oj.uz

Submission #401320

# Submission time Handle Problem Language Result Execution time Memory
401320 2021-05-09T20:42:02 Z hgmhc 앱 (KOI13_app) C++14
21 / 21
 5 ms 4172 KB 
#include <iostream>
using namespace std;
const int maxn = 100, maxp = 1e4;
int n, M, m[maxn+1], c[maxn+1], dp[maxn+1][maxp+1];
 
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> M;
    for (int i = 1; i <= n; ++i) cin >> m[i];
    for (int i = 1; i <= n; ++i) cin >> c[i];
    for (int k = 1; k <= n; ++k) {
        for (int p = 0; p <= maxp; ++p) {
            dp[k][p] = dp[k-1][p];
            if (p-c[k] >= 0)
                dp[k][p] = max(dp[k][p], dp[k-1][p-c[k]]+m[k]);
        }
    }
    for (int p = 0; p <= maxp; ++p) {
        if (dp[n][p] >= M) {
            cout << p;
            return 0;
        }
    }
}

Subtask #1
3.15 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 1 ms 972 KB Output is correct
4 Correct 1 ms 972 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 1088 KB Output is correct

Subtask #2
3.15 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 844 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 332 KB Output is correct

Subtask #3
3.15 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1868 KB Output is correct
2 Correct 2 ms 1228 KB Output is correct
3 Correct 3 ms 1996 KB Output is correct
4 Correct 3 ms 1996 KB Output is correct
5 Correct 2 ms 2124 KB Output is correct
6 Correct 3 ms 1996 KB Output is correct

Subtask #4
3.15 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1100 KB Output is correct
2 Correct 2 ms 1996 KB Output is correct
3 Correct 2 ms 1740 KB Output is correct
4 Correct 2 ms 2112 KB Output is correct
5 Correct 2 ms 1868 KB Output is correct
6 Correct 2 ms 2252 KB Output is correct

Subtask #5
3.15 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4172 KB Output is correct
2 Correct 4 ms 3788 KB Output is correct
3 Correct 4 ms 4044 KB Output is correct
4 Correct 4 ms 3916 KB Output is correct
5 Correct 3 ms 2892 KB Output is correct
6 Correct 2 ms 2256 KB Output is correct

Subtask #6
3.15 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3788 KB Output is correct
2 Correct 3 ms 2884 KB Output is correct
3 Correct 4 ms 3012 KB Output is correct
4 Correct 4 ms 4044 KB Output is correct
5 Correct 3 ms 2892 KB Output is correct
6 Correct 4 ms 4144 KB Output is correct

Subtask #7
2.1 / 2.1

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