oj.uz

Submission #548826

# Submission time Handle Problem Language Result Execution time Memory
548826 2022-04-14T12:34:51 Z jack715 Journey (NOI18_journey) C++14
100 / 100
 168 ms 10184 KB 
#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<vector<int> > reach(n, vector<int>(m, 0));
    reach[0][0] = 1;

    for (int i = 0; i < n-1; i++) {
        vector<int> sum(m+1);
        sum[0] = reach[i][0];
        for (int j = 1; j < m; j++)
            sum[j] = sum[j-1] + reach[i][j];
        for (int p = 0; p < h; p++) {
            if (path[i][p].ff <= i)
                continue;
            for (int j = path[i][p].ss; j < m; j++) {
                reach[path[i][p].ff][j] = min((long long)500000001, sum[j-path[i][p].ss]+reach[path[i][p].ff][j]);
            }
        }
    }

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 49 ms 6888 KB Output is correct
8 Correct 72 ms 10184 KB Output is correct
9 Correct 25 ms 3280 KB Output is correct
10 Correct 168 ms 4644 KB Output is correct