제출 #784451

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
784451		tosivanmak	Feast (NOI19_feast)	C++17	100 / 100	407 ms	23792 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];
bool check(long double lambda) {
	dp[0][0] = {0, 0}, dp[0][1] = {-300000*1e9, 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-5){
       ld mid=(l+r)/2;
       if(check(mid)){
           l=mid;
       }
       else{
           r=mid;
       }
   }
//    cout<<dpval<<" "<<lab<<" "<<l<<"\n";
bool orz=check(l);
ld store=k;
   return max(dp[n][0],dp[n][1]).first+store*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<<(ll)round(ans)<<"\n";
}

컴파일 시 표준 에러 (stderr) 메시지

feast.cpp: In function 'long double Aliens()':
feast.cpp:32:6: warning: unused variable 'orz' [-Wunused-variable]
   32 | bool orz=check(l);
      |      ^~~

• 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