Submission #1193763

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193763		repsak	Feast (NOI19_feast)	C++20	4 / 100	175 ms	8628 KiB

feast

//O(N log N)
// https://oj.uz/problem/view/NOI19_feast
// Lagrangian Relaxation

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int N, K;
vector<int> values;
ll totalScore = 0;

bool solve(ll cost){

    vector<ll> run(N + 1);
    vector<ll> no(N + 1);
    vector<ll> uses(N + 1);

    for(int i = 1; i <= N; i++){
        int val = values[i - 1];

        uses[i] = uses[i - 1];

        run[i] = run[i - 1] + val;
        ll potential = no[i - 1] + val - cost;
       
        if(potential > run[i]){
            run[i] = potential;
            uses[i] += 1;
        }

        if(run[i] < 0){
            run[i] = 0;
            uses[i]--;
        }

        no[i] = max({
            no[i - 1], 
            run[i]
        });
    }

    ll c = uses[N] + 1;
    totalScore = max(run[N], no[N]) + cost * c;

    return c > K;
}

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

    cin >> N >> K;
    values.resize(N);
    for(int i = 0; i < N; i++){
        cin >> values[i];
    }

    ll low = 0; ll high = 1e18;

    while(low < high){
        ll mid = (low + high) / 2;

        if(solve(mid)){ //if c >= K
            low = mid + 1;
        }else{
            high = mid;
        }
    }

    solve(low);
    cout << totalScore;


    // int A_; cin >> A_;
    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 18
• Subtask 4: 0 / 10
• Subtask 5: 0 / 11
• Subtask 6: 0 / 20
• Subtask 7: 0 / 29