oj.uz

Submission #591246

# Submission time Handle Problem Language Result Execution time Memory
591246 2022-07-07T06:45:25 Z dryeab Split the sequence (APIO14_sequence) C++17
0 / 100
 9 ms 1612 KB 
#include <bits/stdc++.h>

using ll = long long;

using namespace std;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, k;
    cin >> n >> k;

    vector<ll> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        a[i] += a[i - 1];
    }

    int m, l, r;
    ll M = 0;

    for (int i = 1; i <= n; ++i) {
        if ((a[n] - a[i]) * a[i] > M) {
            m = i;
            M = (a[n] - a[i]) * a[i];
        }
    }

    priority_queue<pair<pair<ll, int>, pair<int, int>>> pq;
    pq.push({{M, m}, {1, n}});

    ll res = 0;
    vector<int> ord;

    while (k) {

        auto top = pq.top();
        pq.pop();

        M = top.first.first, m = top.first.second;
        l = top.second.first, r = top.second.second;

        ord.push_back(m); // add the divided point

        res += M;

        if (l != r) {
            M = 0;
            int m2;
            for (int i = l; i <= m; ++i) {
                if ((a[m] - a[i]) * (a[i] - a[l - 1]) > M) {
                    m2 = i;
                    M = (a[m] - a[i]) * (a[i] - a[l - 1]);
                }
            }

            pq.push({{M, m2}, {l, m}});

            M = 0;
            for (int i = m + 1; i <= r; ++i) {
                if (((a[r] - a[i]) * (a[i] - a[m])) > M) {
                    m2 = i;
                    M = (a[r] - a[i]) * (a[i] - a[m]);
                }
            }

            pq.push({{M, m2}, {m + 1, r}});
        }

        k--;
    }

    cout << res << '\n';

    for (auto x : ord)
        cout << x << " ";
}

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 Incorrect 1 ms 212 KB contestant didn't find the optimal answer: 951 < 999
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB contestant didn't find the optimal answer: 1093726 < 1093956
2 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 1 ms 212 KB contestant found the optimal answer: 311760000 == 311760000
3 Correct 1 ms 320 KB contestant found the optimal answer: 1989216017013 == 1989216017013
4 Correct 1 ms 212 KB contestant found the optimal answer: 1499437552673 == 1499437552673
5 Incorrect 0 ms 212 KB contestant didn't find the optimal answer: 1019625813 < 1019625819
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1252 KB contestant found the optimal answer: 19795776960 == 19795776960
2 Correct 8 ms 1228 KB contestant found the optimal answer: 19874432173 == 19874432173
3 Incorrect 9 ms 1612 KB contestant didn't find the optimal answer: 497009314607795353 < 497313449256899208
4 Halted 0 ms 0 KB -