Submission #548794

#	Time	Username	Problem	Language	Result	Execution time	Memory
548794		jack715	Journey (NOI18_journey)	C++14	43 / 100	47 ms	428 KiB

journey

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pp pop_back
#define mp make_pair
#define bb back
#define ff first
#define ss second
#define int long long

using namespace std;

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, m, h;
    cin >> n >> m >> h;
    vector<vector<pair<int, int> > > path(n, vector<pair<int, int> >(h));
    
    for (int i = 0; i < n-1; i++)
    for (int j = 0; j < h; j++) 
        cin >> path[i][j].ff >> path[i][j].ss;
    
    vector<int> ans(m+5, 0);
    vector<vector<int> > reach(n, vector<int>(m, 0));
    reach[0][0] = 1;

    for (int i = 0; i < n-1; i++) {
        for (int k = 0; k < m; k++) {
            for (int p = 0; p < h; p++) {
                if (path[i][p].ff <= i)
                    continue;
                for (int j = path[i][p].ss; j+k < m; j++)
                    reach[path[i][p].ff][j+k] += reach[i][k];
            }
        }
    }

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

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