oj.uz

답안 #987518

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
987518 2024-05-22T23:23:55 Z tfgs Feast (NOI19_feast) C++17
41 / 100
 32 ms 11608 KB 
#include <bits/stdc++.h>
using namespace std;
#define int int64_t

#ifdef LOCAL
#include "algo/debug.h"
#endif

#define f first
#define s second
template<class T> using V = vector<T>; 
using vi = V<int>;
using vb = V<bool>;
using vs = V<string>;

#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x) 
#define pb push_back
#define lb lower_bound
#define ub upper_bound
template<class T> int lwb(V<T>& a, const T& b) { return lb(all(a),b)-begin(a); }
template<class T> int upb(V<T>& a, const T& b) { return ub(all(a),b)-begin(a); }
template<class T> bool ckmin(T& a, const T& b) { return a > b ? a=b, true : false; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a=b, true : false; }

const int max_n = 1e5;
array<int, 2> dp[max_n][2];
int n, k;
vi a;
// returns {score, number of segments} with penalty lmb for making a new subarray
array<int, 2> calc(int lmb) {
    memset(dp, 0, sizeof dp);
    // V<V<array<int, 2>>> dp(n, V<array<int, 2>>(2));
    dp[0][1] = {a[0]-lmb, 1};
    for (int i = 1; i < n; i++) {
        dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
        dp[i][1] = max(array<int, 2>{ dp[i-1][0][0]+a[i]-lmb, dp[i-1][0][1]+1 },
                       array<int, 2>{ dp[i-1][1][0]+a[i],     dp[i-1][1][1] });
    }
    return max(dp[n-1][0], dp[n-1][1]);
}

void solve() {
    cin >> n >> k;
    a.resize(n); for (int i = 0; i < n; i++) cin >> a[i];

    // int lo = 0;
    // int hi = 1e18;
    // while (lo < hi) {
        // int mid = (lo + hi + 1) / 2;
        // calc(mid)[1] >= k ? lo = mid : hi = mid - 1;
    // }
    // cout << calc(lo)[0]+lo*k << '\n';
    int lo = -1, hi = 1e18;
    while (hi-lo > 1) {
        int m = (lo+hi)/2;
        auto res = calc(m);
        res[1] >= k ? lo = m : hi = m;
    }
    if (lo == -1) {
        cout << calc(0)[0] << '\n';
        return;
    }
    auto ans = calc(lo);
    cout << ans[0]+lo*k << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 29 ms 11348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 21 ms 11608 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 32 ms 11524 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3420 KB Output is correct
2 Correct 4 ms 3420 KB Output is correct
3 Correct 5 ms 3420 KB Output is correct
4 Correct 5 ms 3420 KB Output is correct
5 Correct 5 ms 3420 KB Output is correct
6 Correct 5 ms 3416 KB Output is correct
7 Correct 5 ms 3420 KB Output is correct
8 Correct 4 ms 3416 KB Output is correct
9 Correct 5 ms 3420 KB Output is correct
10 Correct 4 ms 3420 KB Output is correct

Subtask #5
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3420 KB Output is correct
2 Correct 4 ms 3420 KB Output is correct
3 Correct 5 ms 3420 KB Output is correct
4 Correct 5 ms 3420 KB Output is correct
5 Correct 5 ms 3420 KB Output is correct
6 Correct 5 ms 3416 KB Output is correct
7 Correct 5 ms 3420 KB Output is correct
8 Correct 4 ms 3416 KB Output is correct
9 Correct 5 ms 3420 KB Output is correct
10 Correct 4 ms 3420 KB Output is correct
11 Correct 6 ms 3416 KB Output is correct
12 Correct 5 ms 3420 KB Output is correct
13 Correct 4 ms 3420 KB Output is correct
14 Correct 5 ms 3592 KB Output is correct
15 Correct 5 ms 3420 KB Output is correct
16 Correct 5 ms 3420 KB Output is correct
17 Correct 5 ms 3420 KB Output is correct
18 Correct 5 ms 3420 KB Output is correct
19 Correct 5 ms 3416 KB Output is correct
20 Correct 4 ms 3416 KB Output is correct

Subtask #6
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3420 KB Output is correct
2 Correct 4 ms 3420 KB Output is correct
3 Correct 5 ms 3420 KB Output is correct
4 Correct 5 ms 3420 KB Output is correct
5 Correct 5 ms 3420 KB Output is correct
6 Correct 5 ms 3416 KB Output is correct
7 Correct 5 ms 3420 KB Output is correct
8 Correct 4 ms 3416 KB Output is correct
9 Correct 5 ms 3420 KB Output is correct
10 Correct 4 ms 3420 KB Output is correct
11 Correct 6 ms 3416 KB Output is correct
12 Correct 5 ms 3420 KB Output is correct
13 Correct 4 ms 3420 KB Output is correct
14 Correct 5 ms 3592 KB Output is correct
15 Correct 5 ms 3420 KB Output is correct
16 Correct 5 ms 3420 KB Output is correct
17 Correct 5 ms 3420 KB Output is correct
18 Correct 5 ms 3420 KB Output is correct
19 Correct 5 ms 3416 KB Output is correct
20 Correct 4 ms 3416 KB Output is correct
21 Correct 5 ms 3420 KB Output is correct
22 Correct 5 ms 3420 KB Output is correct
23 Correct 5 ms 3420 KB Output is correct
24 Correct 5 ms 3420 KB Output is correct
25 Correct 5 ms 3420 KB Output is correct
26 Correct 5 ms 3420 KB Output is correct
27 Correct 5 ms 3416 KB Output is correct
28 Correct 5 ms 3420 KB Output is correct
29 Correct 5 ms 3420 KB Output is correct
30 Correct 5 ms 3420 KB Output is correct

Subtask #7
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 29 ms 11348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -