Submission #12205

#	Time	Username	Problem	Language	Result	Execution time	Memory
12205		gs14004	앱 (KOI13_app)	C++98	6.30 / 21	1000 ms	5192 KiB

app

#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
• Subtask 2: 3.15 / 3.15
• Subtask 3: 0 / 3.15
• Subtask 4: 0 / 3.15
• Subtask 5: 0 / 3.15
• Subtask 6: 0 / 3.15
• Subtask 7: 0 / 2.1