Submission #1311200

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311200		aryan	Journey (NOI18_journey)	C++20	100 / 100	1327 ms	5396 KiB

journey

#include<bits/stdc++.h>
using namespace std;

using i64 = long long;


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

    int n,m,h;
    cin >> n >> m >> h;
    vector<vector<pair<int,int>>> adj(n);
    for(int i = 0;i < n - 1;i++){
        for(int j = 0;j < h;j++){
            int v,w;
            cin >> v >> w;
            if(v <= i) continue;
            adj[v].push_back(make_pair(i,w));
        }
    }
    const int inf = 5e8;
    vector<vector<int>> dp(n,vector<int>(m));
    dp[0][0] = 1;
    // no of ways to reach city i such that sum of weights is j
    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
                for(pair<int,int> p : adj[i]){
                    if(dp[i][j] == -1) break;
                    int v = p.first;
                    int w = p.second;
                    if(j - w >= 0){
                        for(int b = 0;b <= j - w;b++){
                            if(dp[v][b] == -1){
                                dp[i][j] = -1;
                                break;
                            } 
                            dp[i][j] +=  dp[v][b];                          
                        }
                    }
                    if(dp[i][j] > inf) dp[i][j] = -1;
           }
        }
    }
    
    for(int i = 0;i < m;i++){
        if(dp[n - 1][i] == -1) cout << inf + 1 << " ";
        else cout << dp[n - 1][i] << " ";
    }
    cout << '\n';
    return 0;
}

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