Submission #997478

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
997478	2024-06-12T11:17:02 Z	vjudge1	Split the sequence (APIO14_sequence)	C++17	0 / 100	1146 ms	131072 KB

sequence

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll N = 1e5 + 100;
const ll K = 205;

ll n, k, a[N], dp[N][K], par[N][K], suff[N];

int main(){
    cin >> n >> k;
    k++;

    for (ll i = 1; i <= n; i ++)
        cin >> a[i];
    for (ll i = n; i > 0; i --)
        suff[i] = suff[i + 1] + a[i];

    for (ll i = n; i > 0; i --){
        for (ll p = 2; p <= k; p ++){
            if (i + p - 1 > n){
                dp[i][p] = -1e18;
                continue;
            }
            dp[i][p] = -1;

            if (p == 2){
                ll poss = n;
                int bad = 0;
                for (ll j = poss; j > i; j --){
                    ll val = dp[j][p - 1] + (suff[i] - suff[j]) * suff[j];
                    if (val > dp[i][p]){
                        dp[i][p] = val;
                        par[i][p] = j;
                    }
                }
            }
            else{
                int bad = 0;
                for (ll j = par[i][p - 1]; j > i; j --){
                    if (dp[j][p - 1] < 0) continue;

                    ll val = dp[j][p - 1] + (suff[i] - suff[j]) * suff[j];
                    if (val > dp[i][p]){
                        dp[i][p] = val;
                        par[i][p] = j;
                    }
                    else break;
                }
            }

            // cout << i << " " << p << " goes to " << par[i][p] << endl;
        }
    }

    cout << dp[1][k] << endl;

    ll cur_i = 1;
    ll cur_k = k;

    while (cur_k > 1){
        cout << par[cur_i][cur_k] - 1 << " ";
        cur_i = par[cur_i][cur_k];
        cur_k--;
    }
    cout << endl;
}

Compilation message

sequence.cpp: In function 'int main()':
sequence.cpp:30:21: warning: unused variable 'bad' [-Wunused-variable]
   30 |                 int bad = 0;
      |                     ^~~
sequence.cpp:40:21: warning: unused variable 'bad' [-Wunused-variable]
   40 |                 int bad = 0;
      |                     ^~~

Subtask #1
0 / 11.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	6492 KB	contestant found the optimal answer: 610590000 == 610590000
2	Correct	1 ms	6492 KB	contestant found the optimal answer: 311760000 == 311760000
3	Correct	1 ms	6492 KB	contestant found the optimal answer: 1989216017013 == 1989216017013
4	Correct	1 ms	6492 KB	contestant found the optimal answer: 1499437552673 == 1499437552673
5	Incorrect	1 ms	6492 KB	contestant didn't find the optimal answer: 917701369 < 1019625819
6	Halted	0 ms	0 KB	-