Submission #3140

#	Time	Username	Problem	Language	Result	Execution time	Memory
3140		club4208	앱 (KOI13_app)	C++98	21 / 21	4 ms	5032 KiB

app

#include <stdio.h>
#define INF 10000001
int d[101][10001];
int m[101], cost[101], n, memory;
int max(int a, int b){
    if(a<b) return b;
    else return a;
}
int main(){
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt', "w", stdout);

    int i, j, sum=0, res=INF;
    scanf("%d %d", &n, &memory);
 
    for(i=1;i<=n;i++) scanf("%d", &m[i]);
    for(i=1;i<=n;i++){ scanf("%d", &cost[i]); sum+=cost[i]; }
 
    for(i=1;i<=n;i++){
        for(j=0;j<=sum;j++){
            int a=j-cost[i];
            d[i][j]=d[i][j-1];
            if(a>=0) d[i][j]=max(d[i-1][a]+m[i], d[i][j]);
            if(i>0) d[i][j]=max(d[i][j], d[i-1][j]);
            if(d[i][j]>=memory && res>=j) res=j;
        }
    }
    printf("%d", res);
    return 0;
}

• 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