oj.uz

답안 #12207

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
12207 2014-12-24T08:44:44 Z gs14004 앱 (KOI13_app) C++
21 / 21
 8 ms 5192 KB 
#include <cstdio>
#include <cstring>
#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;
    if(~dp[x][cost]) return dp[x][cost];
    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(){
    memset(dp,-1,sizeof(dp));
    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

# 결과 실행 시간 메모리 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
6 Correct 0 ms 5192 KB Output is correct

Subtask #2
3.15 / 3.15

# 결과 실행 시간 메모리 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
3.15 / 3.15

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5192 KB Output is correct
2 Correct 0 ms 5192 KB Output is correct
3 Correct 4 ms 5192 KB Output is correct
4 Correct 0 ms 5192 KB Output is correct
5 Correct 0 ms 5192 KB Output is correct
6 Correct 4 ms 5192 KB Output is correct

Subtask #4
3.15 / 3.15

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 5192 KB Output is correct
2 Correct 0 ms 5192 KB Output is correct
3 Correct 4 ms 5192 KB Output is correct
4 Correct 0 ms 5192 KB Output is correct
5 Correct 0 ms 5192 KB Output is correct
6 Correct 0 ms 5192 KB Output is correct

Subtask #5
3.15 / 3.15

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5192 KB Output is correct
2 Correct 8 ms 5192 KB Output is correct
3 Correct 8 ms 5192 KB Output is correct
4 Correct 8 ms 5192 KB Output is correct
5 Correct 4 ms 5192 KB Output is correct
6 Correct 4 ms 5192 KB Output is correct

Subtask #6
3.15 / 3.15

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5192 KB Output is correct
2 Correct 0 ms 5192 KB Output is correct
3 Correct 4 ms 5192 KB Output is correct
4 Correct 8 ms 5192 KB Output is correct
5 Correct 0 ms 5192 KB Output is correct
6 Correct 8 ms 5192 KB Output is correct

Subtask #7
2.1 / 2.1

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5192 KB Output is correct
2 Correct 4 ms 5192 KB Output is correct
3 Correct 4 ms 5192 KB Output is correct
4 Correct 4 ms 5192 KB Output is correct