oj.uz

Submission #147004

# Submission time Handle Problem Language Result Execution time Memory
147004 2019-08-27T03:56:09 Z dongwon0427 Journey (NOI18_journey) C++14
100 / 100
 96 ms 41128 KB 
#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;
            ll tmp = 0;
            for(int l=day;l<m;l++) {
                tmp += num[i][l-day];
                num[nxt][l] += tmp;
                if(num[nxt][l] > 500000001) num[nxt][l] = 500000001;
            }
        }
    }

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #2
23.0 / 23.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 760 KB Output is correct
6 Correct 3 ms 760 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 760 KB Output is correct
6 Correct 3 ms 760 KB Output is correct
7 Correct 96 ms 41128 KB Output is correct
8 Correct 75 ms 24844 KB Output is correct
9 Correct 14 ms 3704 KB Output is correct
10 Correct 57 ms 4216 KB Output is correct