oj.uz

Submission #147002

# Submission time Handle Problem Language Result Execution time Memory
147002 2019-08-27T03:52:35 Z dongwon0427 Journey (NOI18_journey) C++14
69 / 100
 2000 ms 41108 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;
            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.0 / 20.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 #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 376 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 12 ms 888 KB Output is correct
6 Correct 12 ms 820 KB Output is correct

Subtask #4
0 / 31.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
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 12 ms 888 KB Output is correct
6 Correct 12 ms 820 KB Output is correct
7 Correct 135 ms 41108 KB Output is correct
8 Correct 465 ms 24980 KB Output is correct
9 Correct 639 ms 3832 KB Output is correct
10 Execution timed out 2041 ms 4216 KB Time limit exceeded