Submission #926420

#	Time	Username	Problem	Language	Result	Execution time	Memory
926420		idiotcomputer	Split the sequence (APIO14_sequence)	C++11	100 / 100	782 ms	89328 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define pii pair<ll,ll>
#define f first
#define s second

//a + (x-c)^2 > b + (x-c2)^2   
// a + c^2-2cx > b + c2^2 - 2c2x
//a - b + c^2 - c2^2 > 2x * (c-c2)
//b - a + c2^2 - c^2 < 2x * (c2-c)

double find(ll a, ll b, ll c1, ll c2){
    if (c2 == c1){
        return 0;
    }
    return (double) (b-a+c2*c2-c1*c1) / (double) (2*(c2-c1));
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n,k;
    cin >> n >> k;
    
    ll vals[n];
    ll psum[n];
    for (int i =0; i < n; i++){
        cin >> vals[i];
        psum[i] = vals[i];
        if (i>0) psum[i] += psum[i-1];
    }
    
    ll tot = psum[n-1]*psum[n-1];
    int past[n][k+1];
    
    // idx, val
    vector<deque<pii>> all(k);
    ll cval;
    for (int i =0; i < n; i++){
     //   cout << i << ":\n";
        cval = psum[i]*psum[i];
        for (int j =0; j < k; j++){
        //    cout << j+1 << "," << cval << " : ";
            int t = all[j].size();
            while (t >= 2 && find(all[j][0].s,all[j][1].s,psum[all[j][0].f],psum[all[j][1].f]) <= (double) psum[i]){
                all[j].pop_front();
                t -= 1;
            }
            
            while (t >= 2 && find(all[j][t-2].s,all[j][t-1].s,psum[all[j][t-2].f],psum[all[j][t-1].f]) >= find(all[j][t-1].s,cval,psum[all[j][t-1].f],psum[i])){
                all[j].pop_back();
                t -= 1;
            }
            all[j].push_back({i,cval});
        /*    for (int k = 0; k < all[j].size(); k++){
                cout << all[j][k].f << "," << all[j][k].s << " ";
            }
            cout << '\n';*/
            if (t != 0){
                //cout << all[j][0].f << ',' << all[j][0].s << ' ';
                past[i][j+1] = all[j][0].f;
                cval = all[j][0].s + (psum[i] - psum[all[j][0].f]) * (psum[i] - psum[all[j][0].f]);
            } else {
                break;
            }
        }
       // cout << '\n';
    }
    tot -= cval;
 //   cout << cval << '\n';
    cout << tot/2 << '\n';
    int curr = all[k-1][0].f;
    int t = k;
    while (t > 0){
        cout << curr+1 << " ";
        t--;
        curr = past[curr][t];
    }
    cout << '\n';
    
    
    return 0;
}
/*
7 3 
4 1 3 4 0 2 3 
*/

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:72:9: warning: 'cval' may be used uninitialized in this function [-Wmaybe-uninitialized]
   72 |     tot -= cval;
      |     ~~~~^~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 29 / 29