oj.uz

Submission #1102914

# Submission time Handle Problem Language Result Execution time Memory
1102914 2024-10-19T08:42:49 Z alexdumitru Feast (NOI19_feast) C++17
12 / 100
 157 ms 9288 KB 
#include <iostream>

using ll = int64_t;

const int NMAX = 3e5;

int n, k;
int a[NMAX + 1];
ll sp[NMAX + 1];
ll ans;


void read() {
    std::cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
        sp[i] = sp[i - 1] + a[i];
    }
}

std::pair<ll, int> dp[NMAX + 1];

bool operator < (const std::pair<ll, int> & a, const std::pair<ll, int> & b) {
    if (a.first != b.first)
        return a.first < b.first;
    return a.second < b.second;
}

bool operator > (const std::pair<ll, int> & a, const std::pair<ll, int> & b) {
    if (a.first != b.first)
        return a.first > b.first;
    return a.second > b.second;
}

std::pair<ll, int> operator + (const std::pair<ll, int> & a, const std::pair<ll, int> & b) {
    return std::make_pair(a.first + b.first, a.second + b.second);
}

std::pair<ll, int> ok(ll pen) {
    int idx = 0;
    for (int i = 1; i <= n; i++) {
        //dp[i] = dp[j] + sp[i] - sp[j]
        dp[i] = std::max(dp[i - 1], dp[idx] + std::make_pair(sp[i] - sp[idx] - pen, 1));
        if (dp[i] + std::make_pair(-sp[i], 0) > dp[idx])
            idx = i;
    }
    return dp[n];
}

void solve() {
    ll st = 1;
    ll dr = 3e14;
    while (st <= dr) {
        ll mij = (st + dr) / 2;
        auto v = ok(mij);
        if (v.second <= k) {
            ans = v.first + mij * v.second;
            dr = mij - 1;
        } else {
            st = mij + 1;
        }
    }
}

void write_ans() {
    std::cout << ans << '\n';
}

int main() {
    read();
    solve();
    write_ans();
    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 8264 KB Output is correct
2 Correct 132 ms 8532 KB Output is correct
3 Correct 132 ms 8636 KB Output is correct
4 Correct 157 ms 8520 KB Output is correct
5 Correct 143 ms 8520 KB Output is correct
6 Correct 129 ms 8280 KB Output is correct
7 Correct 137 ms 8264 KB Output is correct
8 Correct 133 ms 8524 KB Output is correct
9 Correct 129 ms 8272 KB Output is correct
10 Correct 131 ms 9288 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 8272 KB Output is correct
2 Correct 90 ms 8520 KB Output is correct
3 Correct 89 ms 8264 KB Output is correct
4 Correct 91 ms 8312 KB Output is correct
5 Correct 129 ms 8264 KB Output is correct
6 Correct 91 ms 8272 KB Output is correct
7 Correct 93 ms 8528 KB Output is correct
8 Correct 132 ms 8520 KB Output is correct
9 Correct 150 ms 8332 KB Output is correct
10 Correct 93 ms 8520 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 125 ms 8372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 8264 KB Output is correct
2 Correct 132 ms 8532 KB Output is correct
3 Correct 132 ms 8636 KB Output is correct
4 Correct 157 ms 8520 KB Output is correct
5 Correct 143 ms 8520 KB Output is correct
6 Correct 129 ms 8280 KB Output is correct
7 Correct 137 ms 8264 KB Output is correct
8 Correct 133 ms 8524 KB Output is correct
9 Correct 129 ms 8272 KB Output is correct
10 Correct 131 ms 9288 KB Output is correct
11 Correct 85 ms 8272 KB Output is correct
12 Correct 90 ms 8520 KB Output is correct
13 Correct 89 ms 8264 KB Output is correct
14 Correct 91 ms 8312 KB Output is correct
15 Correct 129 ms 8264 KB Output is correct
16 Correct 91 ms 8272 KB Output is correct
17 Correct 93 ms 8528 KB Output is correct
18 Correct 132 ms 8520 KB Output is correct
19 Correct 150 ms 8332 KB Output is correct
20 Correct 93 ms 8520 KB Output is correct
21 Incorrect 125 ms 8372 KB Output isn't correct
22 Halted 0 ms 0 KB -