Submission #784422

#	Time	Username	Problem	Language	Result	Execution time	Memory
784422		tosivanmak	Feast (NOI19_feast)	C++17	0 / 100	322 ms	26572 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(ld lambda){
    dp[0][0]={0,0};
    dp[0][1]={-1e18,0};
   for(int i=1;i<=n;i++){
       dp[i][1]={dp[i-1][1].first+arr[i],dp[i-1][1].second};
       if(dp[i-1][0].first+arr[i]-lambda>=dp[i][1].first){
           dp[i][1]={dp[i-1][0].first+arr[i]-lambda,dp[i-1][0].second+1};
       }
       if(dp[i-1][1].first>dp[i-1][0].first){
           dp[i][0]={dp[i-1][1].first,dp[i-1][1].second};
       }
       else if(dp[i-1][1].first==dp[i-1][0].first){
           if(dp[i-1][1].second>dp[i-1][0].second){
               dp[i][0]=dp[i-1][0];
           }
           else{
               dp[i][0]=dp[i-1][1];
           }
       }
       else{
           dp[i][0]=dp[i-1][0];
       }
   }
   if(dp[n][0].first>dp[n][1].first){
       dpval=dp[n][0].first;
       lab=dp[n][0].second;
      return dp[n][0].second<=k;
   }
   else if(dp[n][0].first==dp[n][1].first){
       dpval=dp[n][0].first;
       lab=min(dp[n][0].second,dp[n][1].second);
         return min(dp[n][0].second,dp[n][1].second)<=k;
   }
   else{
       dpval=dp[n][1].first;
       lab=dp[n][1].second;
        return dp[n][1].second<=k;
   }
}
ld Aliens(){
    ld l=0,r=1e9*300000;
   while(r-l>=1e-6){
       ld mid=(l+r)/2;
       if(check(mid)){
           r=mid;
       }
       else{
           l=mid;
       }
   }
//    cout<<dpval<<" "<<lab<<" "<<l<<"\n";
   return dpval+lab*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<<ans<<"\n";
}

• 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