Submission #1098844

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1098844	2024-10-10T08:26:33 Z	raul2008487	Split the sequence (APIO14_sequence)	C++17	0 / 100	9 ms	5976 KB

sequence

    #include<bits/stdc++.h>

#define ll long long
#define pb push_back
#define in insert
#define fi first
#define se second
#define vl vector<ll>
#define all(v) v.begin(), v.end()
#define endl "\n"

using namespace std;
const int sz = 1e5 + 123; /// mind this
const int MAX = 2e6 + 123;
const int BS = 61;
const ll inf = 1e17;
ll dp[2][sz], part[205][sz], p[sz], n;
bool cmp1(ll x, ll y, ll i){
    return ((dp[0][y] - dp[0][x]) >= (p[y] - p[x]) * (p[n] - p[i]));
}
bool cmp2(ll x, ll y, ll i){
    return ((dp[0][y] - dp[0][x]) * (p[i] - p[y])) <= ((dp[0][i] - dp[0][y]) * (p[y] - p[x]));
}
void solve(){
    ll k, i, j;
    cin >> n >> k;
    vl v(n + 1);
    for(i = 1; i <= n; i++){
        cin >> v[i];
        p[i] = p[i - 1] + v[i];
    }
    deque<ll> dq;
    for(i = 1; i <= k; i++){
        dq.pb(0);
        for(j = 1; j <= n; j++){
            while(dq.size() > 1 && cmp1(dq[0], dq[1], j)){
                dq.pop_front();
            }
            ll cut = dq.front();
            dp[1][j] = dp[0][cut] + (p[j] - p[cut]) * (p[n] - p[j]);
            // cout << j << ' ' << cut << ' ' << dp[1][j] << endl;
            part[i][j] = cut;
            while(dq.size() > 1 && cmp2(dq.back(), dq[dq.size() - 2], j)){
                dq.pop_back();
            }
            dq.pb(j);
        }
        dq.clear();
        for(j = 1; j <= n; j++){
            dp[0][j] = dp[1][j];
        }
    }
    ll ans = -1, idx = -1;
    for(i = 1; i <= n; i++){
        if(dp[0][i] > ans){
            ans = dp[0][i], idx = i;
        }
    }
    cout << ans << endl;
    for(i = k; i > 0; i--){
        cout << idx << ' ';
        idx = part[i][idx];
    }
    cout << endl;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}
/*
7 3
4 1 3 4 0 2 3
*/

Subtask #1
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	contestant found the optimal answer: 108 == 108
2	Correct	0 ms	348 KB	contestant found the optimal answer: 999 == 999
3	Correct	0 ms	348 KB	contestant found the optimal answer: 0 == 0
4	Correct	0 ms	348 KB	contestant found the optimal answer: 1542524 == 1542524
5	Correct	0 ms	348 KB	contestant found the optimal answer: 4500000000 == 4500000000
6	Correct	0 ms	348 KB	contestant found the optimal answer: 1 == 1
7	Correct	0 ms	464 KB	contestant found the optimal answer: 1 == 1
8	Correct	1 ms	344 KB	contestant found the optimal answer: 1 == 1
9	Correct	0 ms	344 KB	contestant found the optimal answer: 100400096 == 100400096
10	Correct	0 ms	348 KB	contestant found the optimal answer: 900320000 == 900320000
11	Incorrect	1 ms	348 KB	contestant didn't find the optimal answer: 3498210227 < 3698080248
12	Halted	0 ms	0 KB	-

Subtask #2
0 / 11.0

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

Subtask #3
0 / 11.0

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