Submission #73812

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
73812	2018-08-29T04:53:15 Z	노영훈(#2275)	Schools (IZhO13_school)	C++11	0 / 100	737 ms	196240 KB

school

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=5010;
const ll linf=2e17;

int n, p, q;
pii X[MX];
ll ans, D[MX][MX];

ll d(int i, int cnt){
	ll &res=D[i][cnt];
	if(res!=-1) return res;
	res=d(i-1, cnt);
	if(cnt>0) res=max(res, d(i-1,cnt-1)+(cnt>q ? X[i].first : X[i].second));
	return res;
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin>>n>>p>>q;
	for(int i=1; i<=n; i++) cin>>X[i].first>>X[i].second;
	sort(X+1, X+n+1, [](pii &a, pii &b){ return a.first-a.second < b.first-b.second; });

	for(int i=0; i<=n; i++) for(int j=0; j<=n; j++) D[i][j]=-1;
	for(int j=0; j<=n; j++) D[0][j]=-linf;
	D[0][0]=0;
	for(int i=1; i<=p+q; i++) D[i][0]=0;
	for(int i=p+q+1; i<=n; i++) D[i][0]=-linf;

/*	for(int i=1; i<=n; i++, cout<<'\n') for(int j=0; j<=n; j++) cout<<d(i,j)<<' ';
	cout<<'\n';
*/
	cout<<d(n, p+q)<<'\n';

	return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	504 KB	Output is correct
2	Correct	2 ms	564 KB	Output is correct
3	Correct	3 ms	564 KB	Output is correct
4	Correct	4 ms	884 KB	Output is correct
5	Correct	3 ms	884 KB	Output is correct
6	Correct	4 ms	1312 KB	Output is correct
7	Correct	342 ms	168112 KB	Output is correct
8	Correct	647 ms	178480 KB	Output is correct
9	Correct	649 ms	181724 KB	Output is correct
10	Correct	682 ms	188472 KB	Output is correct
11	Correct	724 ms	193776 KB	Output is correct
12	Correct	737 ms	196240 KB	Output is correct
13	Runtime error	165 ms	196240 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
14	Halted	0 ms	0 KB	-