제출 #1123017

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1123017		Monchito	Feast (NOI19_feast)	C++20	100 / 100	579 ms	40320 KiB

feast

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

#define fst first
#define snd second
#define fore(i,a,b) for(auto i=a; i<b; i++)
#define forn(i,n) fore(i,0,n)

typedef long long ll;

const int MAXN = 3e5+10;

const ll INF = 1e15;

int n, k;

ll a[MAXN], lambda;
ll dp[MAXN][2], cnt[MAXN][2];

ll solve(int i, int flag){
	if(i==n) return cnt[i][flag]=0;
	ll& ret = dp[i][flag];
	if(ret != -1) return ret;
	cnt[i][flag]=0;
	if(flag==0){
		ret = solve(i+1,0);
		cnt[i][flag]=cnt[i+1][flag];
		if(ret < solve(i,1)-lambda){
			ret = solve(i,1)-lambda;
			cnt[i][flag] = 1 + cnt[i][1];
		}
		else if(ret == solve(i,1)-lambda){
			cnt[i][flag]=min(cnt[i][flag],1+cnt[i][1]);
		}
	}
	else{
		ret = a[i] + solve(i+1,1);
		cnt[i][flag]=cnt[i+1][flag];
		if(ret < a[i]+solve(i+1,0)){
			ret=a[i]+solve(i+1,0);
			cnt[i][flag] = cnt[i+1][0];
		}
		else if(ret==a[i]+solve(i+1,0)){
			cnt[i][flag]=min(cnt[i][flag],cnt[i+1][0]);
		}
	}
	return ret;
}

int main(){
	scanf("%d%d",&n,&k);
	forn(i,n) cin>>a[i];
	ll l = 0, r = INF;
	while(r>l){
		ll mid = l+(r-l)/2;
		lambda = mid;
		memset(dp,-1,sizeof(dp));
		solve(0,0);
		if(cnt[0][0] <= k) r=mid;
		else l=mid+1;
	}
	lambda = r;
	memset(dp,-1,sizeof(dp));
	solve(0,0);
	//printf("%lld %lld\n", cnt[0][0], r);
	ll ans = dp[0][0] + cnt[0][0] * lambda;
	printf("%lld\n", ans);
	return 0;
}

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

feast.cpp: In function 'int main()':
feast.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         scanf("%d%d",&n,&k);
      |         ~~~~~^~~~~~~~~~~~~~

• 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