oj.uz

Submission #146970

# Submission time Handle Problem Language Result Execution time Memory
146970 2019-08-27T01:52:00 Z gs14004 Journey (NOI18_journey) C++17
100 / 100
 217 ms 10968 KB 
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
const int MAXN = 10005;
const int mod = 5e8 + 1;

int n, m, h;
vector<pi> nxt[MAXN];
int dp[405][MAXN];
int add[405][MAXN];

int main(){
	scanf("%d %d %d",&n,&m,&h);
	for(int i=0; i<n-1; i++){
		for(int j=0; j<h; j++){
			int x, y; scanf("%d %d",&x,&y);
			if(x > i){
				nxt[i].emplace_back(x, y);
			}
		}
	}
	dp[0][0] = 1;
	for(int i=0; i<m; i++){
		for(int j=0; j<n; j++){
			add[i+1][j] = min(add[i+1][j] + add[i][j], mod);
			dp[i][j] = min(dp[i][j] + add[i][j], mod);
			for(auto &k : nxt[j]){
				if(i + k.second < m){
					add[i + k.second][k.first] = 
					min(add[i + k.second][k.first] + dp[i][j], mod);
				}
			}
		}
		cout << dp[i][n-1] << " ";
	}
}

Compilation message

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

Subtask #1
20.0 / 20.0

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

Subtask #2
23.0 / 23.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 2 ms 632 KB Output is correct
5 Correct 4 ms 1400 KB Output is correct
6 Correct 5 ms 1400 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 2 ms 632 KB Output is correct
5 Correct 4 ms 1400 KB Output is correct
6 Correct 5 ms 1400 KB Output is correct
7 Correct 79 ms 4088 KB Output is correct
8 Correct 123 ms 10968 KB Output is correct
9 Correct 40 ms 6596 KB Output is correct
10 Correct 217 ms 7676 KB Output is correct