Submission #544686

#	Time	Username	Problem	Language	Result	Execution time	Memory
544686		pokmui9909	서울에서 경산까지 (KOI17_travel)	C++17	100 / 100	41 ms	13516 KiB

travel

#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 / 29
• Subtask 2: 71 / 71