Submission #1296931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296931		chaitanyamehta	Feast (NOI19_feast)	C++20	0 / 100	265 ms	21308 KiB

feast

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

#define int long long
int n , k;
const int INF = (long long)300000 * 1000000000;
const long double EPS = 1e-3;
const int N = 3 * 1e6 + 2;
vector<int> a;
pair<long double ,int> dp[N][2]; 

bool check(long double lambda){
    dp[0][1] = {-INF , 0}, dp[0][0] = {0 , 0};

    for(int i = 1 ; i <= n ; i++){
        dp[i][0] = max(dp[i-1][0] , dp[i-1][1]);

        dp[i][1] = max(make_pair(dp[i-1][1].first+a[i] , dp[i-1][1].second) ,make_pair(dp[i-1][0].first +   a[i] - lambda , dp[i-1][0].second + 1));
    }
    return max(dp[n][0] , dp[n][1]).second >= k;
}

long double solve(){

    long double l = 0;
    long double r = INF;
    
    while(l + EPS < r){
        long double m = (l +r) / 2;
        if(check(m)){
            l = m;
        }
        else{
            r = m;
        }
    }
    return l;
}


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

    long double lambda = solve();   

    check(lambda);
    long double res = (long long)round((k * lambda) + max(dp[n][1] , dp[n][0]).first);
 
    
    cout << res;
}

• Subtask 1: 0 / 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