oj.uz

Submission #12205

# Submission time Handle Problem Language Result Execution time Memory
12205 2014-12-24T08:44:16 Z gs14004 앱 (KOI13_app) C++
6.3 / 21
 1000 ms 5192 KB 
#include <cstdio>
#include <algorithm>
using namespace std;

int n,m,a[105],c[105], dp[105][10005];

int f(int x, int cost){
    if(x == 0) return 0;
    int ret = f(x-1,cost);
    if(cost >= c[x-1]){
        ret = max(ret,f(x-1,cost - c[x-1]) + a[x-1]);
    }
    return dp[x][cost] = ret;
}

int main(){
    scanf("%d %d",&n,&m);
    for (int i=0; i<n; i++) {
        scanf("%d",&a[i]);
    }
    for (int i=0; i<n; i++) {
        scanf("%d",&c[i]);
    }
    int s = 0, e = 10000;
    while (s != e) {
        int mid = (s+e)/2;
        if(f(n,mid) >= m) e = mid;
        else s = mid+1;
    }
    printf("%d",s);
}

Subtask #1
3.15 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5192 KB Output is correct
2 Correct 40 ms 5192 KB Output is correct
3 Correct 36 ms 5192 KB Output is correct
4 Correct 16 ms 5192 KB Output is correct
5 Correct 0 ms 5192 KB Output is correct
6 Correct 40 ms 5192 KB Output is correct

Subtask #2
3.15 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5192 KB Output is correct
2 Correct 0 ms 5192 KB Output is correct
3 Correct 0 ms 5192 KB Output is correct
4 Correct 0 ms 5192 KB Output is correct
5 Correct 0 ms 5192 KB Output is correct

Subtask #3
0.0 / 3.15

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 5188 KB Program timed out
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 84 ms 5192 KB Output is correct
2 Execution timed out 1000 ms 5188 KB Program timed out
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 3.15

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 5188 KB Program timed out
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 3.15

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 5188 KB Program timed out
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 2.1

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 5188 KB Program timed out
2 Halted 0 ms 0 KB -