제출 #1296391

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1296391		chaitanyamehta	Feast (NOI19_feast)	C++20	30 / 100	131 ms	2752 KiB

feast

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

#define int long long
int n , k;
const int INF = 1e15;
vector<int> a;

pair<int , int> better(pair<int , int> opt1 , pair<int , int> opt2){
    if(opt1.first != opt2.first){
        return (opt1.first > opt2.first) ? opt1 : opt2;
    }
    else{
        return (opt1.second >= opt2.second) ? opt1 : opt2;
    }
}

pair<int , int> check(int lambda){
    pair<int , int> dp1 = {-INF , 0}, dp0 = {0 , 0};

    for(int i = 0 ; i < n ; i++){
        pair<int , int> opt1 = {(dp1.first == -INF) ? -INF :   dp1.first + a[i] , dp1.second};
        pair<int , int> opt2 = {dp0.first + a[i] - lambda , dp0.second + 1};
    
        dp1 = better(opt1 , opt2);
        dp0 = better(dp1 , dp0);
    }
    return dp0;
}

int solve(){
    int l = -1e15;
    int r = 1e15;
    int ans = 0;
    while(l < r){
        int m = l + ((r-l+1) / 2);
        if(check(m).second >= k){
            l = m;
            ans = m;
        }
        else{
            r = m -1;
        }
    }
    return l;
}


signed main(){
    cin>>n >> k;
    a.resize(n);
    for(int i = 0 ; i < n ;i++)cin>>a[i];

    int ans = solve();   

    pair<int , int> fans = check(ans);

    cout << max(0LL , fans.first + (ans * k));
}

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