oj.uz

Submission #1102952

# Submission time Handle Problem Language Result Execution time Memory
1102952 2024-10-19T09:17:32 Z alexdumitru Feast (NOI19_feast) C++17
12 / 100
 159 ms 9800 KB 
#include <iostream>


using ll = int64_t;
#define int ll

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 = 0;
    ll dr = 3e14;
    while (st <= dr) {
        ll mij = (st + dr) / 2;
        auto v = ok(mij);
        if (v.second == k) {
            ans = v.first + mij * k;
            return;
        } else if (v.second > k) {
            st = mij + 1;
        } else {
            dr = mij - 1;
        }
    }

    auto v = ok(st);

    ans = v.first + st * v.second;
}

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

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

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 9372 KB Output is correct
2 Correct 136 ms 9500 KB Output is correct
3 Correct 134 ms 9800 KB Output is correct
4 Correct 139 ms 9588 KB Output is correct
5 Correct 144 ms 9732 KB Output is correct
6 Correct 159 ms 9548 KB Output is correct
7 Correct 133 ms 9544 KB Output is correct
8 Correct 133 ms 9544 KB Output is correct
9 Correct 125 ms 9392 KB Output is correct
10 Correct 131 ms 9648 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 9556 KB Output is correct
2 Correct 68 ms 9676 KB Output is correct
3 Correct 62 ms 9604 KB Output is correct
4 Correct 94 ms 9600 KB Output is correct
5 Correct 80 ms 9452 KB Output is correct
6 Correct 64 ms 9476 KB Output is correct
7 Correct 95 ms 9764 KB Output is correct
8 Correct 81 ms 9700 KB Output is correct
9 Correct 80 ms 9516 KB Output is correct
10 Correct 106 ms 9624 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 103 ms 9524 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 2552 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 2552 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 2552 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 9372 KB Output is correct
2 Correct 136 ms 9500 KB Output is correct
3 Correct 134 ms 9800 KB Output is correct
4 Correct 139 ms 9588 KB Output is correct
5 Correct 144 ms 9732 KB Output is correct
6 Correct 159 ms 9548 KB Output is correct
7 Correct 133 ms 9544 KB Output is correct
8 Correct 133 ms 9544 KB Output is correct
9 Correct 125 ms 9392 KB Output is correct
10 Correct 131 ms 9648 KB Output is correct
11 Correct 69 ms 9556 KB Output is correct
12 Correct 68 ms 9676 KB Output is correct
13 Correct 62 ms 9604 KB Output is correct
14 Correct 94 ms 9600 KB Output is correct
15 Correct 80 ms 9452 KB Output is correct
16 Correct 64 ms 9476 KB Output is correct
17 Correct 95 ms 9764 KB Output is correct
18 Correct 81 ms 9700 KB Output is correct
19 Correct 80 ms 9516 KB Output is correct
20 Correct 106 ms 9624 KB Output is correct
21 Incorrect 103 ms 9524 KB Output isn't correct
22 Halted 0 ms 0 KB -