# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
95417 |
2019-02-01T03:55:50 Z |
easrui |
None (JOI14_ho_t2) |
C++14 |
|
17 ms |
504 KB |
#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[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<=1e4; 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=1e4; j>=C[i]; j--){
D[j][i%2] = min(D[j][(i+1)%2],D[j-C[i]][(i+1)%2] + E[i]);
if(j!=1e4) 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;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
380 KB |
Output is correct |
2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
376 KB |
Output is correct |
2 |
Correct |
16 ms |
376 KB |
Output is correct |
3 |
Correct |
17 ms |
504 KB |
Output is correct |
4 |
Correct |
16 ms |
504 KB |
Output is correct |
5 |
Correct |
17 ms |
504 KB |
Output is correct |
6 |
Incorrect |
16 ms |
504 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
380 KB |
Output is correct |
2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |