#include <bits/stdc++.h>
using namespace std;
const int MM = 1e4+5;
const int MN = 505;
int M,N,P[MM],S[MM],C[MN],E[MN],ans,res;
int D[10*MM][2];
int main()
{
//freopen("input.txt","r",stdin);
ios_base::sync_with_stdio(0),cin.tie(0);
cin >> M >> N;
for(int i=1; i<=M; i++)
cin >> P[i];
sort(P+1,P+M+1,greater<int>());
for(int i=1; i<=M; i++){
S[i] = S[i-1] + P[i];
}
for(int i=1; i<=1e5; i++) D[i][0] = D[i][1] = 1e9;
for(int i=1; i<=N; i++) cin >> C[i] >> E[i];
for(int i=1; i<=N; i++){
for(int j=1e5; j>=0; j--){
if(j>=C[i]) D[j][i%2] = min(D[j][(i+1)%2],D[j-C[i]][(i+1)%2] + E[i]);
D[j][i%2] = min(D[j][(i+1)%2],D[j][i%2]);
if(j!=1e5) D[j][i%2] = min(D[j][i%2],D[j+1][i%2]);
}
}
//cout << D[2][N%2];
for(int i=0; i<=M; i++){
ans = max(ans,S[i]-D[i][N%2]);
}
cout << ans;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
1116 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1144 KB |
Output is correct |
| 3 |
Correct |
7 ms |
1144 KB |
Output is correct |
| 4 |
Correct |
6 ms |
1272 KB |
Output is correct |
| 5 |
Correct |
7 ms |
1272 KB |
Output is correct |
| 6 |
Correct |
6 ms |
1144 KB |
Output is correct |
| 7 |
Correct |
6 ms |
1144 KB |
Output is correct |
| 8 |
Correct |
6 ms |
1144 KB |
Output is correct |
| 9 |
Correct |
7 ms |
1272 KB |
Output is correct |
| 10 |
Correct |
7 ms |
1272 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
170 ms |
1144 KB |
Output is correct |
| 2 |
Correct |
171 ms |
1144 KB |
Output is correct |
| 3 |
Correct |
173 ms |
1248 KB |
Output is correct |
| 4 |
Correct |
170 ms |
1272 KB |
Output is correct |
| 5 |
Correct |
170 ms |
1244 KB |
Output is correct |
| 6 |
Correct |
170 ms |
1116 KB |
Output is correct |
| 7 |
Correct |
136 ms |
1272 KB |
Output is correct |
| 8 |
Correct |
170 ms |
1272 KB |
Output is correct |
| 9 |
Correct |
167 ms |
1272 KB |
Output is correct |
| 10 |
Correct |
168 ms |
1276 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
1116 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1144 KB |
Output is correct |
| 3 |
Correct |
7 ms |
1144 KB |
Output is correct |
| 4 |
Correct |
6 ms |
1272 KB |
Output is correct |
| 5 |
Correct |
7 ms |
1272 KB |
Output is correct |
| 6 |
Correct |
6 ms |
1144 KB |
Output is correct |
| 7 |
Correct |
6 ms |
1144 KB |
Output is correct |
| 8 |
Correct |
6 ms |
1144 KB |
Output is correct |
| 9 |
Correct |
7 ms |
1272 KB |
Output is correct |
| 10 |
Correct |
7 ms |
1272 KB |
Output is correct |
| 11 |
Correct |
170 ms |
1144 KB |
Output is correct |
| 12 |
Correct |
171 ms |
1144 KB |
Output is correct |
| 13 |
Correct |
173 ms |
1248 KB |
Output is correct |
| 14 |
Correct |
170 ms |
1272 KB |
Output is correct |
| 15 |
Correct |
170 ms |
1244 KB |
Output is correct |
| 16 |
Correct |
170 ms |
1116 KB |
Output is correct |
| 17 |
Correct |
136 ms |
1272 KB |
Output is correct |
| 18 |
Correct |
170 ms |
1272 KB |
Output is correct |
| 19 |
Correct |
167 ms |
1272 KB |
Output is correct |
| 20 |
Correct |
168 ms |
1276 KB |
Output is correct |
| 21 |
Correct |
168 ms |
1272 KB |
Output is correct |
| 22 |
Correct |
169 ms |
1272 KB |
Output is correct |
| 23 |
Correct |
170 ms |
1272 KB |
Output is correct |
| 24 |
Correct |
175 ms |
1272 KB |
Output is correct |
| 25 |
Correct |
175 ms |
1400 KB |
Output is correct |
| 26 |
Correct |
166 ms |
1272 KB |
Output is correct |
| 27 |
Correct |
170 ms |
1240 KB |
Output is correct |
| 28 |
Correct |
167 ms |
1272 KB |
Output is correct |
| 29 |
Correct |
168 ms |
1288 KB |
Output is correct |
| 30 |
Correct |
168 ms |
1400 KB |
Output is correct |
