oj.uz

Submission #286505

# Submission time Handle Problem Language Result Execution time Memory
286505 2020-08-30T13:50:37 Z BeanZ Split the sequence (APIO14_sequence) C++14
0 / 100
 72 ms 131076 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(mid - 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;
                }
        }
        DP(k, l, mid - 1, optl, best);
        DP(k, mid + 1, 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:30:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   30 |                 freopen("VietCT.INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
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.OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB contestant found the optimal answer: 108 == 108
2 Correct 1 ms 384 KB contestant found the optimal answer: 999 == 999
3 Correct 1 ms 384 KB contestant found the optimal answer: 0 == 0
4 Incorrect 0 ms 384 KB contestant didn't find the optimal answer: 1542522 < 1542524
5 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB contestant didn't find the optimal answer: 1093844 < 1093956
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 640 KB contestant didn't find the optimal answer: 514120000 < 610590000
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1952 KB contestant didn't find the optimal answer: 21487275 < 21503404
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 16640 KB contestant found the optimal answer: 1818678304 == 1818678304
2 Incorrect 10 ms 16640 KB contestant didn't find the optimal answer: 1300787987 < 1326260195
3 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 72 ms 131076 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -