Submission #1170575

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170575		zrzzrz	Feast (NOI19_feast)	C++20	71 / 100	33 ms	63304 KiB

feast

#include <bits/stdc++.h>
using namespace std;
int n,k,a[300005],x;
long long f[2005][2005][2],g[300005][2][2],L;
int main(){
	scanf("%d%d",&n,&k);
	long long sum=0;
	for (int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if (a[i]<0) x=i,L=sum;
		sum+=a[i];
	}
	if (n<=2000&&k<=2000){
		memset(f,0x80,sizeof f);
		f[0][0][0]=0;
		for (int i=1;i<=n;i++) for (int j=0;j<=k;j++){
			f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]);
			f[i][j][1]=max(f[i-1][j][1],j?f[i-1][j-1][0]:(long long)-1e18)+a[i];
		}
		long long ans=0;
		for (int i=0;i<=k;i++) ans=max({ans,f[n][i][0],f[n][i][1]});
		printf("%lld\n",ans);
	}
	else if (k==1){
		memset(g,0x80,sizeof g);
		g[0][0][0]=0;
		for (int i=1;i<=n;i++) for (int j=0;j<=k;j++){
			g[i][j][0]=max(g[i-1][j][0],g[i-1][j][1]);
			g[i][j][1]=max(g[i-1][j][1],j?g[i-1][j-1][0]:(long long)-1e18)+a[i];
		}
		long long ans=0;
		for (int i=0;i<=k;i++) ans=max({ans,g[n][i][0],g[n][i][1]});
		printf("%lld\n",ans);
	}
	else{
		if (!x) printf("%lld\n",sum);
		else{
			if (k==1) printf("%lld\n",max({sum,L,sum-L-a[x]}));
			else printf("%lld\n",sum-a[x]);
		}
	}
	return 0;
}

Compilation message (stderr)

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

• 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