Submission #867447

#	Time	Username	Problem	Language	Result	Execution time	Memory
867447		JoksimKaktus	Split the sequence (APIO14_sequence)	C++17	0 / 100	5 ms	1628 KiB

sequence

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(0);
    int n;
    long double k;
    cin >> n >> k;
    vector <ll> pre(n+1);
    pre[0]=0;
    vector <int> v(n+1);
    for(int i = 1;i <= n;i++){
        cin >> v[i];
        pre[i] = pre[i-1]+v[i];
    }
    long double limit = (pre[n]/(k+1));
    ll cur = 0;
    long double dif = 0;
    int l = 0;
    ll res = 0;
    vector <int> ind;
    for(int i = 1;i <=n && ind.size() < k;i++){
        if(cur == 0){
            cur += v[i];
            continue;
        }
        if(cur + v[i] >= limit+dif){
            if(abs((cur + v[i])-limit+dif) == abs(cur-limit+dif)){
                if(dif > 0){
                    res += (pre[i-1] - pre[l])*(pre[n] - pre[i-1]);
                    l = i-1;
                    dif += cur - limit;
                    cur = v[i];
                    ind.push_back(i-1);
                }else{
                    res += (pre[i] - pre[l])*(pre[n] - pre[i]);
                    l = i;
                    dif += (cur + v[i])-limit;
                    cur = 0;
                    ind.push_back(i);
                }
            }else if(abs((cur + v[i])-limit+dif) > abs(cur-limit+dif)){
                res += (pre[i-1] - pre[l])*(pre[n] - pre[i-1]);
                l = i-1;
                dif += cur - limit;
                cur = v[i];
                ind.push_back(i-1);
            }else{
                res += (pre[i] - pre[l])*(pre[n] - pre[i]);
                l = i;
                dif += (cur + v[i])-limit;
                cur = 0;
                ind.push_back(i);
            }
        }else{
            cur += v[i];
        }
    }
    cout << res << "\n";
    for(int i : ind){
        cout << i << " ";
    }
    return 0;
}

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