oj.uz

Submission #286501

# Submission time Handle Problem Language Result Execution time Memory
286501 2020-08-30T13:47:37 Z BeanZ Split the sequence (APIO14_sequence) C++14
0 / 100
 2000 ms 1408 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define endl '\n'

const int N = 1e5 + 5;
ll dp[N][2];
ll opt[N][205];
ll a[N];
void DP(ll k, ll l, ll r, ll optl, ll optr){
        if (l > r) return;
        ll mid = (l + r) >> 1;
        dp[mid][1] = -1e18;
        ll best = optl;
        for (int i = optl; i <= min(r - 1, optr); i++){
                if (dp[mid][1] < (dp[i][0] + a[i] * (a[mid] - a[i]))){
                        dp[mid][1] = dp[i][0] + a[i] * (a[mid] - a[i]);
                        opt[mid][k] = i;
                }
        }
        if (l == r) return;
        DP(k, l, mid, optl, best);
        DP(k, mid, r, best, optr);
}
int main(){
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        if (fopen("VietCT.INP", "r")){
                freopen("VietCT.INP", "r", stdin);
                freopen("VietCT.OUT", "w", stdout);
        }
        ll n, k;
        cin >> n >> k;
        for (int i = 1; i <= n; i++) cin >> a[i], a[i] = a[i] + a[i - 1];
        for (int i = 1; i <= k; i++){
                DP(i, 1, n, 1, n);
                for (int j = 1; j <= n; j++){
                        dp[j][0] = dp[j][1];
                }
        }
        cout << dp[n][1] << endl;
        for (int i = k; i >= 1; i--){
                cout << opt[n][i] << " ";
                n = opt[n][i];
        }
}
/*
7 3
4 1 3 4 0 2 3
*/

Compilation message

sequence.cpp: In function 'int main()':
sequence.cpp:31:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   31 |                 freopen("VietCT.INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:32:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   32 |                 freopen("VietCT.OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2081 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2078 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2072 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2041 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2021 ms 512 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2071 ms 1408 KB Time limit exceeded
2 Halted 0 ms 0 KB -