oj.uz

Submission #2918

# Submission time Handle Problem Language Result Execution time Memory
2918 2013-08-03T14:01:24 Z kipa00 앱 (KOI13_app) C++
21 / 21
 4 ms 4996 KB 
#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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4996 KB Output is correct
2 Correct 0 ms 4996 KB Output is correct
3 Correct 0 ms 4996 KB Output is correct
4 Correct 0 ms 4996 KB Output is correct
5 Correct 0 ms 4996 KB Output is correct
6 Correct 0 ms 4996 KB Output is correct

Subtask #2
3.15 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4996 KB Output is correct
2 Correct 0 ms 4996 KB Output is correct
3 Correct 0 ms 4996 KB Output is correct
4 Correct 0 ms 4996 KB Output is correct
5 Correct 0 ms 4996 KB Output is correct

Subtask #3
3.15 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4996 KB Output is correct
2 Correct 0 ms 4996 KB Output is correct
3 Correct 0 ms 4996 KB Output is correct
4 Correct 0 ms 4996 KB Output is correct
5 Correct 0 ms 4996 KB Output is correct
6 Correct 0 ms 4996 KB Output is correct

Subtask #4
3.15 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4996 KB Output is correct
2 Correct 0 ms 4996 KB Output is correct
3 Correct 0 ms 4996 KB Output is correct
4 Correct 0 ms 4996 KB Output is correct
5 Correct 0 ms 4996 KB Output is correct
6 Correct 0 ms 4996 KB Output is correct

Subtask #5
3.15 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4996 KB Output is correct
2 Correct 0 ms 4996 KB Output is correct
3 Correct 4 ms 4996 KB Output is correct
4 Correct 4 ms 4996 KB Output is correct
5 Correct 0 ms 4996 KB Output is correct
6 Correct 0 ms 4996 KB Output is correct

Subtask #6
3.15 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4996 KB Output is correct
2 Correct 0 ms 4996 KB Output is correct
3 Correct 0 ms 4996 KB Output is correct
4 Correct 4 ms 4996 KB Output is correct
5 Correct 0 ms 4996 KB Output is correct
6 Correct 4 ms 4996 KB Output is correct

Subtask #7
2.1 / 2.1

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4996 KB Output is correct
2 Correct 0 ms 4996 KB Output is correct
3 Correct 0 ms 4996 KB Output is correct
4 Correct 0 ms 4996 KB Output is correct