oj.uz

Submission #689876

# Submission time Handle Problem Language Result Execution time Memory
689876 2023-01-29T15:44:08 Z dsyz Journey (NOI18_journey) C++17
100 / 100
 42 ms 10832 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N,M,H;
	cin>>N>>M>>H;
	pair<ll,ll> flight[N - 1][H];
	for(ll i = 0;i < N - 1;i++){
		for(ll j = 0;j < H;j++){
			cin>>flight[i][j].first>>flight[i][j].second;
		}
	}
	ll dp[N][M];
	memset(dp,0,sizeof(dp));
	dp[0][0] = 1;
	for(ll i = 0;i < N - 1;i++){
		for(ll days = 1;days < M;days++){
			dp[i][days] += dp[i][days - 1];
		}
		for(ll j = 0;j < H;j++){
			if(flight[i][j].first > i){
				ll a = i;
				ll b = flight[i][j].first;
				ll k = flight[i][j].second;
				for(ll days = 0;days < M - k;days++){
					dp[b][days + k] += dp[i][days];
					dp[b][days + k] = min(dp[b][days + k],500000001ll);
				}
			}
		}
	}
	for(ll j = 0;j < M;j++){
		cout<<min(dp[N - 1][j],500000001ll)<<" ";
	}
	cout<<'\n';
}

Compilation message

journey.cpp: In function 'int main()':
journey.cpp:24:8: warning: unused variable 'a' [-Wunused-variable]
   24 |     ll a = i;
      |        ^

Subtask #1
20.0 / 20.0

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

Subtask #2
23.0 / 23.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 336 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 37 ms 7816 KB Output is correct
8 Correct 39 ms 10832 KB Output is correct
9 Correct 9 ms 3148 KB Output is correct
10 Correct 42 ms 4564 KB Output is correct