fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long int;
  4. #define inf 1000000000000000LL
  5. #define mod 1000000007LL
  6. #define FOR(i,a,b) for(ll i = a; i < b; i++)
  7.  
  8. void solve() {
  9.     ll n,k;
  10.     cin >> n >> k;
  11.     vector <ll> l1(n); FOR(i,0,n) cin >> l1[i];
  12.     vector <ll> pos(k+1, inf);
  13.     for (int i = 0; i < n; i++){
  14.         if (pos[l1[i]] == inf) pos[l1[i]] = i;
  15.     }
  16.     for (int i = k - 1; i >= 0; i--){
  17.         pos[i] = min(pos[i], pos[i+1]);
  18.     }
  19.     ll dp[k+1][k+1];
  20.     FOR(i,0,k+1)FOR(j,0,k+1) dp[i][j] = -inf;
  21.     dp[0][0] = 0;
  22.     for (ll i = 0; i <= k; i++){
  23.         if (pos[i] == inf) continue;
  24.         for (ll j = i - 1; j >= 0; j--){
  25.             if (pos[j] == inf) continue;
  26.             for (ll cost = k; cost >= i; cost--){
  27.                 dp[i][cost] = max(dp[i][cost], dp[j][cost - i] + j * (pos[i] - pos[j]));
  28.             }
  29.         }
  30.     }
  31.     ll answ = 0;
  32.     FOR(i,0,k+1){
  33.         if (pos[i] == inf) continue;
  34.         FOR(j,0,k+1){
  35.             answ = max(answ, dp[i][j] + i * (n - pos[i]));
  36.         }
  37.     }
  38.     cout << answ << "\n";
  39. }
  40.  
  41. int main() {
  42.     // ios::sync_with_stdio(false);
  43.     // cin.tie(nullptr);
  44.  
  45.     ll t = 1;
  46.     cin >> t;
  47.     while (t--) {
  48.         solve();
  49.     }
  50.  
  51.     return 0;
  52. }
Runtime error #stdin #stdout #stderr 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/5UW1cs
language:
C++14 (clang 8.0)
created:
2 hours ago
visibility:
secret

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!