Submission #676476

#	Time	Username	Problem	Language	Result	Execution time	Memory
676476		penguin133	Journey (NOI18_journey)	C++17	100 / 100	120 ms	70768 KiB

journey

#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 (stderr)

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

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