oj.uz

답안 #1102951

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1102951 2024-10-19T09:16:28 Z alexdumitru Feast (NOI19_feast) C++17
12 / 100
 157 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;
        }
    }

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

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

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

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 127 ms 9544 KB Output is correct
2 Correct 127 ms 9684 KB Output is correct
3 Correct 130 ms 9800 KB Output is correct
4 Correct 130 ms 9544 KB Output is correct
5 Correct 127 ms 9632 KB Output is correct
6 Correct 125 ms 9356 KB Output is correct
7 Correct 143 ms 9544 KB Output is correct
8 Correct 157 ms 9736 KB Output is correct
9 Correct 124 ms 9544 KB Output is correct
10 Correct 130 ms 9544 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 80 ms 9544 KB Output is correct
2 Correct 59 ms 9772 KB Output is correct
3 Correct 58 ms 9552 KB Output is correct
4 Correct 88 ms 9552 KB Output is correct
5 Correct 81 ms 9488 KB Output is correct
6 Correct 58 ms 9544 KB Output is correct
7 Correct 97 ms 9584 KB Output is correct
8 Correct 92 ms 9544 KB Output is correct
9 Correct 82 ms 9356 KB Output is correct
10 Correct 92 ms 9756 KB Output is correct

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 105 ms 9552 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 127 ms 9544 KB Output is correct
2 Correct 127 ms 9684 KB Output is correct
3 Correct 130 ms 9800 KB Output is correct
4 Correct 130 ms 9544 KB Output is correct
5 Correct 127 ms 9632 KB Output is correct
6 Correct 125 ms 9356 KB Output is correct
7 Correct 143 ms 9544 KB Output is correct
8 Correct 157 ms 9736 KB Output is correct
9 Correct 124 ms 9544 KB Output is correct
10 Correct 130 ms 9544 KB Output is correct
11 Correct 80 ms 9544 KB Output is correct
12 Correct 59 ms 9772 KB Output is correct
13 Correct 58 ms 9552 KB Output is correct
14 Correct 88 ms 9552 KB Output is correct
15 Correct 81 ms 9488 KB Output is correct
16 Correct 58 ms 9544 KB Output is correct
17 Correct 97 ms 9584 KB Output is correct
18 Correct 92 ms 9544 KB Output is correct
19 Correct 82 ms 9356 KB Output is correct
20 Correct 92 ms 9756 KB Output is correct
21 Incorrect 105 ms 9552 KB Output isn't correct
22 Halted 0 ms 0 KB -