답안 #544686

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
544686 2022-04-02T14:23:25 Z pokmui9909 서울에서 경산까지 (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;
}
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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