Submission #1161447

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161447		alexander707070	Feast (NOI19_feast)	C++20	22 / 100	20 ms	4168 KiB

feast

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

int n,a[MAXN],k;
long long pref[MAXN],ans;
bool used[MAXN];

int main(){

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin>>n>>k;

	for(int i=1;i<=n;i++){
		cin>>a[i];
		pref[i]=a[i]+pref[i-1];
	}

	for(int i=1;i<=k;i++){
		int last=0,mins=0,l,r;
		long long best=0;

		for(int f=1;f<=n;f++){
			if(used[f]){
				last=f; mins=f;
				continue;
			}else{
				if(pref[f]-pref[mins]>best){
					best=pref[f]-pref[mins];
					l=mins+1; r=f;
				}

				if(pref[f]<pref[mins])mins=f;
			}
		}

		if(best==0)break;

		ans+=best;
		for(int f=l;f<=r;f++)used[f]=true;
	}

	cout<<ans<<"\n";

	return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 0 / 8
• Subtask 3: 18 / 18
• Subtask 4: 0 / 10
• Subtask 5: 0 / 11
• Subtask 6: 0 / 20
• Subtask 7: 0 / 29