fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. int n, k;
  5. long long a[400001], c[400001], st[35], dp[400001][31], kq;
  6. unordered_map<int, long long> ma[31];
  7. void nhap(){
  8.  
  9.     cin >> n >> k;
  10.     for(int i = 1; i <= n; i++){
  11.         cin >> a[i];
  12.         c[i] = a[i] - i + 1e6;
  13.     }
  14. }
  15. void solvetoiuu(){
  16.     for(int i = 1; i <= n; i++){
  17.         for(int j = 0; j <= k; j++){
  18.             if(j == 0)dp[i][j] = a[i];
  19.             else dp[i][j] = 0;
  20.             dp[i][j] = max(dp[i][j], ma[j][c[i]] + a[i]);
  21.             if(j > 0){
  22.                 dp[i][j] = max(dp[i][j], st[j-1] + a[i]);
  23.             }
  24.             ma[j][c[i]] = max(ma[j][c[i]], dp[i][j]);
  25.             st[j] = max(st[j], dp[i][j]);
  26.             kq = max(kq, dp[i][j]);
  27.         }
  28.     }
  29.     cout << kq;
  30. }
  31. int main(){
  32.     ios_base::sync_with_stdio(0);
  33.     cin.tie(0); cout.tie(0);
  34.     nhap();
  35.     solvetoiuu();
  36.     return 0;
  37. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/8WET1J
language:
C++14 (clang 8.0)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!