Submission #784446

#	Time	Username	Problem	Language	Result	Execution time	Memory
784446		tosivanmak	Feast (NOI19_feast)	C++17	71 / 100	365 ms	26956 KiB

feast

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double

ll n,k;
ld arr[300005];
pair<ld,ll> dp[300005][2];
ld dpval,lab;
bool check(long double lambda) {
	dp[0][0] = {0, 0}, dp[0][1] = {-1e18, 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 + arr[i], dp[i - 1][1].second),
		        make_pair(dp[i - 1][0].first + arr[i] - lambda,
		                  dp[i - 1][0].second + 1));
	}
	return max(dp[n][0], dp[n][1]).second >= k;
}
ld Aliens(){
    ld l=0,r=1e9*300000;
   while(r-l>=1e-4){
       ld mid=(l+r)/2;
       if(check(mid)){
           l=mid;
       }
       else{
           r=mid;
       }
   }
//    cout<<dpval<<" "<<lab<<" "<<l<<"\n";
   return max(dp[n][0],dp[n][1]).first+k*l;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }
    ld ans=Aliens();
     cout<<(long long)round(ans)<<"\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: 0 / 29