Submission #200432

#	Time	Username	Problem	Language	Result	Execution time	Memory
200432		wilwxk	Journey (NOI18_journey)	C++14	100 / 100	103 ms	35808 KiB

journey

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 1e4+5;
const int MAXM = 405;
const ll MOD = 500000001LL;
ll dp[MAXN][MAXM];
vector<pair<int, int> > g[MAXN];
int n, m, x;

int main() {
	scanf("%d %d %d", &n, &m, &x);
	for(int i = 0; i < n-1; i ++) {
		for(int j = 0; j < x; j++) {
			int a, b; scanf("%d %d", &a, &b);
			if(a <= i) continue; 
			g[a].push_back({i, b});
		}
	}

	dp[0][0] = 1;
	for(int i = 1; i < n; i++) {
		for(int j = 0; j < m; j++) {
			for(auto edge : g[i]) {
				int k = j-edge.second;
				if(k < 0) continue;
				dp[i][j] += dp[edge.first][k];
				if(dp[i][j] > MOD) break;
			}
			// printf("%d %d >> %lld\n", i, j, dp[i][j]);
		}
		for(int j = 1; j < m; j++) dp[i][j] += dp[i][j-1], dp[i][j] = min(dp[i][j], MOD+10);
	}

	for(int i = 0; i < m; i++) printf("%lld ", min(dp[n-1][i], MOD));
}

Compilation message (stderr)

journey.cpp: In function 'int main()':
journey.cpp:13:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &m, &x);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
journey.cpp:16:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int a, b; scanf("%d %d", &a, &b);
              ~~~~~^~~~~~~~~~~~~~~~~

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