Submission #2918

#	Time	Username	Problem	Language	Result	Execution time	Memory
2918		kipa00	앱 (KOI13_app)	C++98	21 / 21	4 ms	4996 KiB

app

#include <cstdio>
using namespace std;

int T[100][10001];
int mem[100], cost[100];
int N, memto;

int main() {
    int i, j;
    scanf("%d %d", &N, &memto);
    for (i=0; i<N; ++i) {
        scanf("%d", &mem[i]);
    }
    for (i=0; i<N; ++i) {
        scanf("%d", &cost[i]);
    }

    for(j = 10000; j >= cost[0]; j--) {
        T[0][j] =  mem[0];
    }
    for (i=1; i<N; ++i) {
        for (j = 0; j < cost[i]; j++) T[i][j] = T[i - 1][j];
        for (j=cost[i]; j<=10000; ++j) {
            T[i][j] = T[i - 1][j];
            if (T[i][j] < T[i - 1][j - cost[i]] + mem[i]) {
                T[i][j] = T[i - 1][j - cost[i]] + mem[i];
            }
        }
    }
    for (i=0; i<=10001; ++i) {
        if (T[N - 1][i] >= memto) {
            break;
        }
    }
    printf("%d\n", i);
    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