oj.uz

Submission #127866

# Submission time Handle Problem Language Result Execution time Memory
127866 2019-07-10T07:35:38 Z 김세빈(#3108) Long Distance Coach (JOI17_coach) C++14
0 / 100
 6 ms 5112 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pll;

vector <pll> V[202020];
pll P[202020];
ll X[202020];
ll dp[202020];
ll x, n, m, w, k, ans;

int main()
{
	ll i, j, l, r, v, s;
	
	scanf("%lld%lld%lld%lld%lld", &x, &n, &m, &w, &k);
	
	for(i=1; i<=n; i++){
		scanf("%lld", X + i);
	}
	
	sort(X + 1, X + n + 1);
	
	X[++n] = x;
	
	for(i=1; i<=m; i++){
		scanf("%lld%lld", &P[i].first, &P[i].second);
	}
	
	sort(P + 1, P + m + 1);
	
	for(i=1; i<=n; i++){
		if(X[i - 1] % k + (X[i] - X[i - 1]) < k){
			l = X[i - 1] % k + 1; r = X[i] % k; v = X[i] / k;
		}
		else{
			l = 1; r = X[i] % k; v = X[i] / k;
		}
		
		r = lower_bound(P + 1, P + m + 1, pll(r, 1e18)) - P - 1;
		if(r >= 1 && l <= r) V[r].emplace_back(l, v);
	}
	
	dp[0] = (x / k + 1) * w;
	
	for(i=1; i<=m; i++){
		if(P[i].first % k < x % k) dp[i] = dp[i - 1] + (x / k + 1) * w;
		else dp[i] = dp[i - 1] + x / k * w;
		
		for(pll &t: V[i]){
			for(j=i, s=0; j>=1; j--){
				s += P[j].second + w * t.second;
				dp[i] = min(dp[i], dp[j - 1] + s);
			}
		}
	}
	
	printf("%lld\n", dp[m]);
	
	return 0;
}

Compilation message

coach.cpp: In function 'int main()':
coach.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld%lld%lld", &x, &n, &m, &w, &k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
coach.cpp:21:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", X + i);
   ~~~~~^~~~~~~~~~~~~~~
coach.cpp:29:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", &P[i].first, &P[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 6 ms 5112 KB Output is correct
6 Correct 6 ms 5112 KB Output is correct
7 Correct 6 ms 4984 KB Output is correct
8 Correct 6 ms 5112 KB Output is correct
9 Correct 6 ms 5112 KB Output is correct
10 Incorrect 6 ms 5112 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 6 ms 5112 KB Output is correct
6 Correct 6 ms 5112 KB Output is correct
7 Correct 6 ms 4984 KB Output is correct
8 Correct 6 ms 5112 KB Output is correct
9 Correct 6 ms 5112 KB Output is correct
10 Incorrect 6 ms 5112 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 6 ms 5112 KB Output is correct
6 Correct 6 ms 5112 KB Output is correct
7 Correct 6 ms 4984 KB Output is correct
8 Correct 6 ms 5112 KB Output is correct
9 Correct 6 ms 5112 KB Output is correct
10 Incorrect 6 ms 5112 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 6 ms 5112 KB Output is correct
6 Correct 6 ms 5112 KB Output is correct
7 Correct 6 ms 4984 KB Output is correct
8 Correct 6 ms 5112 KB Output is correct
9 Correct 6 ms 5112 KB Output is correct
10 Incorrect 6 ms 5112 KB Output isn't correct
11 Halted 0 ms 0 KB -