oj.uz

Submission #388216

# Submission time Handle Problem Language Result Execution time Memory
388216 2021-04-10T14:57:53 Z Vladth11 Feast (NOI19_feast) C++14
0 / 100
 1000 ms 5560 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 = 100001;
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
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1071 ms 5380 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

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

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1073 ms 5560 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1071 ms 5380 KB Time limit exceeded
2 Halted 0 ms 0 KB -