oj.uz

Submission #676476

# Submission time Handle Problem Language Result Execution time Memory
676476 2022-12-31T03:34:40 Z penguin133 Journey (NOI18_journey) C++17
100 / 100
 120 ms 70768 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 5e8 + 1;
int dp[10005][405], P[10005][405];
vector<pair<int, int> > v[10005];
main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int n,m,h;
	cin >> n >> m >> h;
	for(int i=0;i<n-1;i++){
		for(int j=0;j<h;j++){		
			int a,b;
			cin >> a >> b;
			v[a].push_back({i,b});
		}
	}
	dp[0][0] = 1;
	for(int i=0;i<m;i++)P[0][i] = 1;
	for(int i=1;i<n;i++){
		for(int j=0;j<m;j++){
			for(auto k : v[i]){
				if(k.first > i || k.second > j)continue;
				dp[i][j] += P[k.first][j-k.second];
				if(dp[i][j] > mod)dp[i][j] = mod;
			}
		}
		P[i][0] = dp[i][0];
		for(int j=1;j<m;j++){
			P[i][j] = P[i][j-1] + dp[i][j];
			if(P[i][j] > mod)P[i][j] = mod;
		}
	}
	for(int i=0;i<m;i++)cout << dp[n-1][i] << " ";
}

Compilation message

journey.cpp:7:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    7 | main(){
      | ^~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
23.0 / 23.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 564 KB Output is correct
3 Correct 1 ms 564 KB Output is correct
4 Correct 1 ms 560 KB Output is correct
5 Correct 2 ms 1236 KB Output is correct
6 Correct 2 ms 1236 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 564 KB Output is correct
3 Correct 1 ms 564 KB Output is correct
4 Correct 1 ms 560 KB Output is correct
5 Correct 2 ms 1236 KB Output is correct
6 Correct 2 ms 1236 KB Output is correct
7 Correct 90 ms 70768 KB Output is correct
8 Correct 107 ms 42704 KB Output is correct
9 Correct 32 ms 6156 KB Output is correct
10 Correct 120 ms 8472 KB Output is correct