oj.uz

Submission #388218

# Submission time Handle Problem Language Result Execution time Memory
388218 2021-04-10T14:59:57 Z Vladth11 Feast (NOI19_feast) C++14
12 / 100
 200 ms 14916 KB 
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;

const ll NMAX = 300001;
const ll nr_of_bits = 16;
const ll MOD = 1000000007;

ll cnt[NMAX][2];
ll dp[NMAX][2];
ll n, k;
ll v[NMAX];

pii OK(ll cost){
    for(ll i = 1; i <= n; i++){
        if(dp[i - 1][1] - cost > dp[i - 1][0]){
            cnt[i][0] = cnt[i - 1][1] + 1;
            dp[i][0] = dp[i - 1][1] - cost;
        }else{
            cnt[i][0] = cnt[i - 1][0];
            dp[i][0] = dp[i - 1][0];
        }
        if(dp[i - 1][1] > dp[i - 1][0]){
            cnt[i][1] = cnt[i - 1][1];
            dp[i][1] = dp[i - 1][1] + v[i];
        }else{
            cnt[i][1] = cnt[i - 1][0];
            dp[i][1] = dp[i - 1][0] + v[i];
        }
    }
    ll cfinal, dfinal;
    if(dp[n][1] - cost > dp[n][0]){
        dfinal = dp[n][1] - cost;
        cfinal = cnt[n][1] + 1;
    }else{
        dfinal = dp[n][0];
        cfinal = cnt[n][0];
    }
    return {dfinal + cost * k, cfinal};
}

int main() {
    //ifstream cin(".in");
    //ofstream cout(".out");
    ll i;
    cin >> n;
    cin >> k;
    for(i = 1; i <= n; i++){
        cin >> v[i];
    }
    ll r = 0, pas = (1 << 30);
    while(pas){
        if(OK(r + pas).second > k)
            r += pas;
        pas /= 2;
    }
    if(OK(r).second > k)
        r++;
    cout << OK(r).first;
    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 11588 KB Output is correct
2 Correct 185 ms 14732 KB Output is correct
3 Correct 172 ms 14916 KB Output is correct
4 Correct 168 ms 14724 KB Output is correct
5 Correct 164 ms 14648 KB Output is correct
6 Correct 165 ms 14468 KB Output is correct
7 Correct 165 ms 14416 KB Output is correct
8 Correct 164 ms 14668 KB Output is correct
9 Correct 175 ms 14388 KB Output is correct
10 Correct 161 ms 14636 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 12212 KB Output is correct
2 Correct 110 ms 13104 KB Output is correct
3 Correct 106 ms 12732 KB Output is correct
4 Correct 110 ms 12860 KB Output is correct
5 Correct 162 ms 14644 KB Output is correct
6 Correct 106 ms 12756 KB Output is correct
7 Correct 108 ms 13124 KB Output is correct
8 Correct 162 ms 14776 KB Output is correct
9 Correct 160 ms 14404 KB Output is correct
10 Correct 107 ms 13072 KB Output is correct

Subtask #3
0 / 18.0

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

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 11588 KB Output is correct
2 Correct 185 ms 14732 KB Output is correct
3 Correct 172 ms 14916 KB Output is correct
4 Correct 168 ms 14724 KB Output is correct
5 Correct 164 ms 14648 KB Output is correct
6 Correct 165 ms 14468 KB Output is correct
7 Correct 165 ms 14416 KB Output is correct
8 Correct 164 ms 14668 KB Output is correct
9 Correct 175 ms 14388 KB Output is correct
10 Correct 161 ms 14636 KB Output is correct
11 Correct 109 ms 12212 KB Output is correct
12 Correct 110 ms 13104 KB Output is correct
13 Correct 106 ms 12732 KB Output is correct
14 Correct 110 ms 12860 KB Output is correct
15 Correct 162 ms 14644 KB Output is correct
16 Correct 106 ms 12756 KB Output is correct
17 Correct 108 ms 13124 KB Output is correct
18 Correct 162 ms 14776 KB Output is correct
19 Correct 160 ms 14404 KB Output is correct
20 Correct 107 ms 13072 KB Output is correct
21 Incorrect 200 ms 11804 KB Output isn't correct
22 Halted 0 ms 0 KB -