Submission #73813

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
73813	2018-08-29T04:59:46 Z	노영훈(#2275)	Schools (IZhO13_school)	C++11	60 / 100	858 ms	243388 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

60.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	376 KB	Output is correct
3	Correct	3 ms	452 KB	Output is correct
4	Correct	6 ms	824 KB	Output is correct
5	Correct	3 ms	824 KB	Output is correct
6	Correct	4 ms	1412 KB	Output is correct
7	Correct	393 ms	168104 KB	Output is correct
8	Correct	609 ms	178392 KB	Output is correct
9	Correct	692 ms	181844 KB	Output is correct
10	Correct	639 ms	188500 KB	Output is correct
11	Correct	855 ms	193788 KB	Output is correct
12	Correct	858 ms	196204 KB	Output is correct
13	Runtime error	171 ms	196204 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
14	Runtime error	123 ms	196204 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
15	Runtime error	23 ms	196204 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
16	Runtime error	451 ms	243388 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
17	Runtime error	42 ms	243388 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
18	Runtime error	10 ms	243388 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
19	Runtime error	10 ms	243388 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
20	Runtime error	13 ms	243388 KB	Execution killed with signal 11 (could be triggered by violating memory limits)