제출 #388218

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
388218		Vladth11	Feast (NOI19_feast)	C++14	12 / 100	200 ms	14916 KiB

feast

#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 / 4
• Subtask 2: 8 / 8
• Subtask 3: 0 / 18
• Subtask 4: 0 / 10
• Subtask 5: 0 / 11
• Subtask 6: 0 / 20
• Subtask 7: 0 / 29