Submission #1116469

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116469		manizare	Feast (NOI19_feast)	C++14	100 / 100	120 ms	13896 KiB

feast

#include <bits/stdc++.h> 

#define pb push_back
#define F first
#define pii pair<int,int> 
#define all(a) a.begin(),a.end()
#define S second 
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define int long long 
using namespace std ;
const int maxn = 3e5 + 10 , mod = 1e9 + 7 , inf = 1e18 ; 
pii dp[maxn][2] ;
int a[maxn] , n , k ; 

void mx(pii &a , pii b){
    if(a.F < b.F || (a.F==b.F && a.S < b.S))a = b; 
}

pii ch(int x){
    dp[0][0] = {0 ,0};
    dp[0][1] = {-inf , 0} ;
    rep(i ,1, n){
        dp[i][0] = dp[i-1][0] ;
        mx(dp[i][0] , dp[i-1][1]) ;
        dp[i][1] = {dp[i-1][1].F+a[i] , dp[i-1][1].S};
        mx(dp[i][1] , {dp[i-1][0].F+a[i]-x , dp[i-1][0].S+1}) ; 
    }
    pii ans = dp[n][0] ;
    mx(ans , dp[n][1]);
    return ans ; 
}

signed main(){
    ios_base::sync_with_stdio(false) ; cin.tie(0) ; 
    cin >> n >> k; 
    rep(i ,1, n){
        cin >> a[i] ;
    }
    int l = 0 , r= 1e18 ;
    while(r-l>1) {
        int mid = (l+r)/2 ; 
        if(ch(mid).S >=  k){
            l = mid ;
        }else{
            r = mid ;
        }
    }
    cout << ch(l).F + l*k << "\n"; 
}

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