oj.uz

Submission #1102942

# Submission time Handle Problem Language Result Execution time Memory
1102942 2024-10-19T09:09:15 Z alexdumitru Feast (NOI19_feast) C++17
0 / 100
 129 ms 9032 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) {
            st = mij + 1;
        } else {
            dr = mij - 1;
        }
    }

    ans = ok(st).first + st * k;
}

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

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

Subtask #1
0 / 4.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 8264 KB Output is correct
2 Correct 92 ms 9032 KB Output is correct
3 Correct 94 ms 8204 KB Output is correct
4 Incorrect 93 ms 8272 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 128 ms 8524 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 Incorrect 129 ms 8208 KB Output isn't correct
2 Halted 0 ms 0 KB -