Submission #736041

#	Time	Username	Problem	Language	Result	Execution time	Memory
736041		Marceantasy	Feast (NOI19_feast)	C++17	100 / 100	618 ms	24544 KiB

feast

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long 
#define ar array
#define rep(i, n) for(int i = 0; i<(int)n; ++i)
 
const int mxN = 3e5+5, M = 1e9+7; 
int n, k;
ll a[mxN];
pair<long double, int> dp[2][mxN];

ll f(long double lambda){
    dp[0][0] = {0, 0};
    dp[1][0] = {a[0]-lambda, 1};
    for(int i = 1; i<n; ++i){
        dp[0][i] = max(dp[0][i-1], dp[1][i-1]);
        dp[1][i] = max(make_pair(dp[0][i-1].first+a[i]-lambda, dp[0][i-1].second+1), make_pair(dp[1][i-1].first+a[i], dp[1][i-1].second));
    }
    return max(dp[0][n-1], dp[1][n-1]).second;
}

void solve(){
    cin >> n >> k;
    rep(i, n) cin >> a[i];
    long double l = 0, r = 1e17;
    rep(_, 100){
        long double m = (l+r+1)/2;
        if(f(m) < k){
            r = m;
        }else{
            l = m;
        }
    }
    long double lambda = l;
    f(lambda);
    cout << (ll)round(lambda * k + max(dp[0][n-1], dp[1][n-1]).first);
}
 
int main(){
#ifdef _DEBUG
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
    std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);
 
    solve();
}

• 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