Submission #1296394

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296394		chaitanyamehta	Feast (NOI19_feast)	C++20	30 / 100	127 ms	2756 KiB

feast

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

#define int long long
int n , k;
const int INF = LLONG_MIN/4;
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 sum = 0;
    for(int i = 0 ;i < n ;i++) sum += llabs(a[i]);
    int l = -sum-5;
    int r = sum+5;
    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);
    __int128 res = (__int128)fans.first + (__int128)ans * (__int128)k;
    long long r = (long long)res;
    
    cout << max(0LL, r);
}

• 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