oj.uz

Submission #670198

# Submission time Handle Problem Language Result Execution time Memory
670198 2022-12-08T09:20:20 Z yyhjin12 Split the sequence (APIO14_sequence) C++17
0 / 100
 13 ms 3796 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef tuple<ll, ll, double, ll> t;

int N, K;
vector<int> psum;

double intersect(t L1, t L2) {
    return (get<1>(L2)-get<1>(L1))/(get<0>(L1)-get<0>(L2));
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    cin >> N >> K; psum.resize(N);
    for (auto &i: psum) cin >> i;
    for (int i=1; i<N; i++) psum[i] = psum[i-1] + psum[i];

    int prev[K][N];
    ll DP[2][N];
    t g;
    
    fill(&prev[0][0], &prev[K-1][N], 0);
    fill(&DP[0][0], &DP[1][N], 0);

    for (int k=0; k<K; k++) {
        deque<t> F; F.push_front(t(0, -1e14, -1, -1));
        for (int i=k+1; i<N; i++) {
            g = t(psum[i-1], DP[(k%2)^1][i-1]-psum[i-1]*psum[i-1], 0, i-1);
            if (get<0>(F.back()) == get<0>(g) && get<1>(F.back()) < get<1>(g)) {
                F.pop_back();
                while (!F.empty()) {
                    g = t(get<0>(g), get<1>(g), intersect(F.back(), g), get<3>(g));
                    if (get<2>(F.back()) < get<2>(g)) break;
                    F.pop_back();
                }
                F.push_back(g);
            }
            else if (get<0>(F.back()) != get<0>(g)) {
                while (!F.empty()) {    
                    g = t(get<0>(g), get<1>(g), intersect(F.back(), g), get<3>(g));
                    if (get<2>(F.back()) < get<2>(g)) break;
                    F.pop_back();
                }
                F.push_back(g);
            }

            ll X = psum[i];
            while (F.size() > 1 && get<2>(F.at(1)) < X) F.pop_front();
            DP[k%2][i] = get<0>(F.front()) * X + get<1>(F.front());
            prev[k][i] = get<3>(F.front());
        }
    }

    cout << DP[(K-1)%2][N-1] << '\n';

    int temp = N-1, q = K-1;
    vector<int> L;
    while (q>=0) {
        L.push_back(prev[q][temp]+1);
        temp = prev[q--][temp];
    }
    sort(L.begin(), L.end());
    for (auto &i: L) cout << i << ' ';
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB contestant found the optimal answer: 108 == 108
2 Correct 0 ms 212 KB contestant found the optimal answer: 999 == 999
3 Correct 0 ms 212 KB contestant found the optimal answer: 0 == 0
4 Correct 0 ms 212 KB contestant found the optimal answer: 1542524 == 1542524
5 Incorrect 0 ms 212 KB declared answer doesn't correspond to the split scheme: declared = 30269803776, real = 4500000000
6 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB contestant found the optimal answer: 1093956 == 1093956
2 Correct 0 ms 212 KB contestant found the optimal answer: 302460000 == 302460000
3 Incorrect 0 ms 212 KB declared answer doesn't correspond to the split scheme: declared = 4155427745305, real = 122453454361
4 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB contestant found the optimal answer: 610590000 == 610590000
2 Correct 0 ms 212 KB contestant found the optimal answer: 311760000 == 311760000
3 Incorrect 1 ms 468 KB declared answer doesn't correspond to the split scheme: declared = 266542021581429, real = 1989216017013
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB contestant found the optimal answer: 21503404 == 21503404
2 Correct 1 ms 340 KB contestant found the optimal answer: 140412195 == 140412195
3 Incorrect 4 ms 1108 KB declared answer doesn't correspond to the split scheme: declared = 16195970589416914, real = 17902527208914
4 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 724 KB declared answer doesn't correspond to the split scheme: declared = 10285334592, real = 1695400000
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 3796 KB declared answer doesn't correspond to the split scheme: declared = 136715067421, real = 7866048541
2 Halted 0 ms 0 KB -