oj.uz

답안 #1101991

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1101991 2024-10-17T09:10:45 Z Zero_OP Feast (NOI19_feast) C++14
18 / 100
 87 ms 14048 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int MAX = 3e5 + 5;
pair<ll, int> dp[2][MAX];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    if(fopen("task.inp", "r")){
        freopen("task.inp", "r", stdin);
        freopen("task.out", "w", stdout);
    }


    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
    }

    auto f = [&](ll lambda) -> pair<ll, int> {
        dp[0][1] = {0, 0};
        dp[1][1] = {a[1] - lambda, 1};
        for(int i = 2; i <= n; ++i){
            dp[0][i] = max(dp[0][i - 1], dp[1][i - 1]);
            dp[1][i] = max(make_pair(dp[0][i - 1].first + a[i] - lambda, dp[0][i - 1].second + 1),
                           make_pair(dp[1][i - 1].first + a[i], dp[1][i - 1].second));
        }

        return max(dp[0][n], dp[1][n]);
    };

    ll l = 0, r = 1e18, ans = 0;
    while(l <= r){
        ll mid = l + r >> 1;
        pair<ll, int> eval = f(mid);
        if(eval.second >= k) ans = eval.first + mid * k, l = mid + 1;
        else r = mid - 1;
    }

    cout << ans << '\n';

    return 0;
}

Compilation message

feast.cpp: In function 'int main()':
feast.cpp:41:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |         ll mid = l + r >> 1;
      |                  ~~^~~
feast.cpp:15:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |         freopen("task.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
feast.cpp:16:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         freopen("task.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

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

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 12024 KB Output is correct
2 Correct 47 ms 12116 KB Output is correct
3 Correct 48 ms 12028 KB Output is correct
4 Incorrect 46 ms 11860 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 81 ms 13900 KB Output is correct
2 Correct 81 ms 13652 KB Output is correct
3 Correct 83 ms 13780 KB Output is correct
4 Correct 86 ms 13644 KB Output is correct
5 Correct 80 ms 13776 KB Output is correct
6 Correct 80 ms 13908 KB Output is correct
7 Correct 80 ms 13920 KB Output is correct
8 Correct 79 ms 13908 KB Output is correct
9 Correct 87 ms 13908 KB Output is correct
10 Correct 82 ms 14048 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 20.0

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

Subtask #7
0 / 29.0

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