| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 13625 |
2015-02-25T14:12:59 Z |
dohyun0324 |
만두 팔기 (JOI14_manju) |
C++ |
|
23 ms |
1204 KB |
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int sum,dap,n,m,a[10010],c[510],e[510],d[2][10010];
int main()
{
int i,j;
scanf("%d %d",&m,&n);
for(i=1;i<=m;i++) scanf("%d",&a[i]);
sort(a+1,a+m+1);
reverse(a+1,a+m+1);
for(i=1;i<=n;i++)
{
scanf("%d %d",&c[i],&e[i]);
}
for(i=0;i<=m;i++) d[0][i]=2147483647;
d[0][0]=0;
for(i=1;i<=n;i++)
{
for(j=0;j<=m;j++) d[i%2][j]=d[(i+1)%2][j];
for(j=0;j<=m;j++)
{
if(d[(i+1)%2][j]!=2147483647) d[i%2][min(m,j+c[i])]=min(d[i%2][min(m,j+c[i])],d[(i+1)%2][j]+e[i]);
}
}
for(i=1;i<=m;i++)
{
sum+=a[i];
if(dap<sum-d[n%2][i]) dap=sum-d[n%2][i];
}
printf("%d",dap);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
1204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1204 KB |
Output is correct |
| 6 |
Correct |
0 ms |
1204 KB |
Output is correct |
| 7 |
Correct |
0 ms |
1204 KB |
Output is correct |
| 8 |
Correct |
0 ms |
1204 KB |
Output is correct |
| 9 |
Correct |
0 ms |
1204 KB |
Output is correct |
| 10 |
Correct |
0 ms |
1204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
1204 KB |
Output is correct |
| 2 |
Correct |
13 ms |
1204 KB |
Output is correct |
| 3 |
Correct |
13 ms |
1204 KB |
Output is correct |
| 4 |
Correct |
13 ms |
1204 KB |
Output is correct |
| 5 |
Correct |
13 ms |
1204 KB |
Output is correct |
| 6 |
Correct |
2 ms |
1204 KB |
Output is correct |
| 7 |
Correct |
10 ms |
1204 KB |
Output is correct |
| 8 |
Correct |
12 ms |
1204 KB |
Output is correct |
| 9 |
Correct |
0 ms |
1204 KB |
Output is correct |
| 10 |
Correct |
13 ms |
1204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
1204 KB |
Output is correct |
| 2 |
Correct |
22 ms |
1204 KB |
Output is correct |
| 3 |
Correct |
22 ms |
1204 KB |
Output is correct |
| 4 |
Correct |
23 ms |
1204 KB |
Output is correct |
| 5 |
Correct |
22 ms |
1204 KB |
Output is correct |
| 6 |
Correct |
18 ms |
1204 KB |
Output is correct |
| 7 |
Correct |
2 ms |
1204 KB |
Output is correct |
| 8 |
Correct |
22 ms |
1204 KB |
Output is correct |
| 9 |
Correct |
21 ms |
1204 KB |
Output is correct |
| 10 |
Correct |
20 ms |
1204 KB |
Output is correct |
