Submission #12207

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

app

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