Submission #126021

#	Time	Username	Problem	Language	Result	Execution time	Memory
126021		TadijaSebez	Cake 3 (JOI19_cake3)	C++11	24 / 100	7 ms	632 KiB

cake3

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll inf=1e18;
const int N=2050;
const ll lim=1e16;
int v[N],c[N],id[N];
ll dp[N];
int main()
{
	int n,m;
	scanf("%i %i",&n,&m);
	for(int i=1;i<=n;i++) scanf("%i %i",&v[i],&c[i]),c[i]*=2,id[i]=i;
	sort(id+1,id+1+n,[&](int i, int j){ return c[i]<c[j];});
	for(int i=1;i<=m;i++) dp[i]=-inf;
	for(int i=1;i<=n;i++)
	{
		dp[m]=max(dp[m],dp[m-1]+v[id[i]]-c[id[i]]);
		for(int j=m-1;j>=2;j--) dp[j]=max(dp[j],dp[j-1]+v[id[i]]);
		dp[1]=max(dp[1],(ll)v[id[i]]+c[id[i]]);
	}
	printf("%lld\n",dp[m]);
	return 0;
}

Compilation message (stderr)

cake3.cpp: In function 'int main()':
cake3.cpp:12:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
cake3.cpp:13:58: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%i %i",&v[i],&c[i]),c[i]*=2,id[i]=i;
                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 19 / 19
• Subtask 3: 0 / 76