oj.uz

Submission #867447

# Submission time Handle Problem Language Result Execution time Memory
867447 2023-10-28T11:57:29 Z JoksimKaktus Split the sequence (APIO14_sequence) C++17
0 / 100
 5 ms 1628 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB contestant found the optimal answer: 108 == 108
2 Correct 0 ms 348 KB contestant found the optimal answer: 999 == 999
3 Incorrect 1 ms 348 KB Unexpected end of file - int32 expected
4 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB contestant found the optimal answer: 610590000 == 610590000
2 Incorrect 0 ms 348 KB Unexpected end of file - int32 expected
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

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

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1628 KB contestant found the optimal answer: 19795776960 == 19795776960
2 Incorrect 5 ms 1628 KB contestant didn't find the optimal answer: 19874432172 < 19874432173
3 Halted 0 ms 0 KB -