oj.uz

Submission #544686

# Submission time Handle Problem Language Result Execution time Memory
544686 2022-04-02T14:23:25 Z pokmui9909 None (KOI17_travel) C++17
100 / 100
 41 ms 13516 KB 
#include <bits/stdc++.h>
using namespace std;

struct st
{
    int a, b, c, d;
}ar[105];

int D[105][100005]; // D[i][j] : 구간 i 를 j분에 이동했을 때 최대 금액

int main()
{
    cin.tie(NULL); cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    int n, k; cin >> n >> k;
    for(int i = 1; i <= n; i++)
        cin >> ar[i].a>>ar[i].b>>ar[i].c>>ar[i].d; // 시간 돈
    D[1][ar[1].a] = ar[1].b;
    D[1][ar[1].c] = max(D[1][ar[1].c], ar[1].d);
    for(int i = 2; i <= n; i++)
    {
        for(int j = 0; j <= k; j++)
        {
            if(D[i - 1][j] == 0) continue;
            if(j + ar[i].a <= k) D[i][j + ar[i].a] = max(D[i][j + ar[i].a], D[i - 1][j] + ar[i].b);
            if(j + ar[i].c <= k) D[i][j + ar[i].c] = max(D[i][j + ar[i].c], D[i - 1][j] + ar[i].d);
        }
    }
    int ans = 0;
    for(int i = 0; i <= k; i++)
        ans = max(ans, D[n][i]);
    cout << ans;
}

Subtask #1
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 0 ms 340 KB Output is correct

Subtask #2
71.0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 12 ms 4224 KB Output is correct
13 Correct 20 ms 7304 KB Output is correct
14 Correct 33 ms 11460 KB Output is correct
15 Correct 35 ms 11828 KB Output is correct
16 Correct 38 ms 12436 KB Output is correct
17 Correct 41 ms 13516 KB Output is correct
18 Correct 36 ms 11724 KB Output is correct
19 Correct 41 ms 12752 KB Output is correct
20 Correct 37 ms 11520 KB Output is correct