제출 #1206197

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1206197		loom	Journey (NOI18_journey)	C++20	100 / 100	35 ms	9796 KiB

journey

#include<bits/stdc++.h>
#define loop(a,b,c,d) for(int a=b; a<c; a+=d)
#define loop2(a,b,c,d) for(int a=b; a>=c; a-=d)
#define bl(i,n) loop(i,0,n,1)
#define bl2(i,n) loop2(i,n,0,1)
#define int long long
#define nl endl
#define g ' '
using namespace std;

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);cout.tie(NULL);

    int n, m, h;
    cin>>n>>m>>h;
    vector<pair<int,int> > flights[n];
    bl(i,n-1){
        bl(_,h){
            int a, b;
            cin>>a>>b;
            if(a <= i) continue;
            flights[a].push_back(make_pair(i, b));
        }
    }

    int last = 0;
    vector<vector<int> > dp(n, vector<int>(m, 0));
    dp[0][0] = 1;
    for(int i=1; i<n; i++){
        for(int j=0; j<m; j++){
            if(j >= 1) dp[i][j] = dp[i][j-1];
            for(auto from : flights[i]){
                if(dp[i][j] >= 500000001){
                    dp[i][j] = 500000001;
                    break;
                }
                if(j >= from.second) dp[i][j] += dp[from.first][j - from.second];
            }

            if(dp[i][j] >= 500000001){
                dp[i][j] = 500000001;
            }

            if(i == n-1) cout<<dp[i][j]<<g;
        }
    }

    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 23 / 23
• Subtask 3: 26 / 26
• Subtask 4: 31 / 31