Submission #147002

#	Time	Username	Problem	Language	Result	Execution time	Memory
147002		dongwon0427	Journey (NOI18_journey)	C++14	69 / 100	2041 ms	41108 KiB

journey

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;


int n,m,h;
pii graph[10005][105];

ll num[10005][405];
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>m>>h;
    for(int i=0;i<n-1;i++) {
        for(int j=0;j<h;j++) cin>>graph[i][j].first>>graph[i][j].second;
    }
    num[0][0] = 1;
    for(int i=0;i<n-1;i++) {
        for(int j=0;j<h;j++) {
            if(graph[i][j].first <= i) continue;
            int nxt = graph[i][j].first;
            int day = graph[i][j].second;
            for(int k=day;k<m;k++) {
                for(int l=k;l<m;l++) {
                    num[nxt][l] += num[i][l-k];
                    if(num[nxt][l] > 500000001) num[nxt][l] = 500000001;
                }
                //if(num > 50000001) num = 50000001;
            }
        }
    }

    for(int i=0;i<m;i++) cout<<num[n-1][i]<<' ';
    return 0;
}

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