oj.uz

Submission #10126

# Submission time Handle Problem Language Result Execution time Memory
10126 2014-10-15T12:30:42 Z gs14004 만두 팔기 (JOI14_manju) C++
100 / 100
 96 ms 20904 KB 
#include <cstdio>
#include <cstring>
#include <algorithm>

int m,n,a[10005];
int sm[10005];

int bv[505],bc[505];
int dp[505][10005];

int cmp(int a, int b){return a>b;}

int f(int pos, int got){
    if(pos == n || got >= m) return sm[got<m?got:m];
    if(dp[pos][got]) return dp[pos][got];
    return dp[pos][got]=std::max(f(pos+1,got),f(pos+1,got+bv[pos])-bc[pos]);
}

int main(){
    scanf("%d %d",&m,&n);
    for (int i=0; i<m; i++) {
        scanf("%d",&a[i]);
    }
    std::sort(a,a+m,cmp);
    for (int i=1; i<=m; i++) {
        sm[i]=sm[i-1]+a[i-1];
    }
    for (int i=0; i<n; i++) {
        scanf("%d %d",&bv[i],&bc[i]);
    }
 //   memset(dp,-1,sizeof(dp));
    printf("%d",f(0,0));
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 20904 KB Output is correct
2 Correct 0 ms 20904 KB Output is correct
3 Correct 0 ms 20904 KB Output is correct
4 Correct 0 ms 20904 KB Output is correct
5 Correct 0 ms 20904 KB Output is correct
6 Correct 0 ms 20904 KB Output is correct
7 Correct 0 ms 20904 KB Output is correct
8 Correct 0 ms 20904 KB Output is correct
9 Correct 0 ms 20904 KB Output is correct
10 Correct 0 ms 20904 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 20904 KB Output is correct
2 Correct 4 ms 20904 KB Output is correct
3 Correct 16 ms 20904 KB Output is correct
4 Correct 12 ms 20904 KB Output is correct
5 Correct 16 ms 20904 KB Output is correct
6 Correct 4 ms 20904 KB Output is correct
7 Correct 4 ms 20904 KB Output is correct
8 Correct 16 ms 20904 KB Output is correct
9 Correct 4 ms 20904 KB Output is correct
10 Correct 8 ms 20904 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 20904 KB Output is correct
2 Correct 92 ms 20904 KB Output is correct
3 Correct 88 ms 20904 KB Output is correct
4 Correct 92 ms 20904 KB Output is correct
5 Correct 96 ms 20904 KB Output is correct
6 Correct 68 ms 20904 KB Output is correct
7 Correct 16 ms 20904 KB Output is correct
8 Correct 96 ms 20904 KB Output is correct
9 Correct 80 ms 20904 KB Output is correct
10 Correct 84 ms 20904 KB Output is correct