oj.uz

Submission #146968

# Submission time Handle Problem Language Result Execution time Memory
146968 2019-08-27T01:51:26 Z gs14004 Journey (NOI18_journey) C++17
69 / 100
 76 ms 3952 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[MAXN][405];
int add[MAXN][405];

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 888 KB Output is correct
6 Correct 4 ms 888 KB Output is correct

Subtask #4
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 888 KB Output is correct
6 Correct 4 ms 888 KB Output is correct
7 Incorrect 76 ms 3952 KB Output isn't correct
8 Halted 0 ms 0 KB -