oj.uz

Submission #127945

# Submission time Handle Problem Language Result Execution time Memory
127945 2019-07-10T08:54:38 Z 임유진(#3111) Long Distance Coach (JOI17_coach) C++14
0 / 100
 2 ms 376 KB 
#include <stdio.h>
#include <algorithm>

using namespace std;

#define MAXN 2005

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

lint S[MAXN];
pll DC[MAXN];
lint die[MAXN];

int main() {
	int N, M;
	lint X, W, T;
	lint ans = 0ll;

	scanf("%lld%d%d%lld%lld", &X, &N, &M, &W, &T);
	for(int i = 0; i < N; i++) scanf("%lld", S + i);
	for(int i = 0; i < M; i++) scanf("%lld%lld", &DC[i].first, &DC[i].second);

	sort(DC, DC + M);
	sort(S, S + N, [&](lint a, lint b) { return a % T < b % T; } );

	//for(int i = 0; i < M; i++) printf("%lld ", DC[i].first + X / T * T);
	//for(int i = 0; i < M; i++) printf("%lld ", DC[i].first + X / T * T >= T ? X / T : X / T + 1);
	for(int i = 0; i < M; i++) ans += (DC[i].first + X / T * T >= X ? (X - 1) / T : (X - 1) / T + 1) * W;

	for(int i = 0; i < M; i++) if(DC[i].first >= X % T) DC[i].second += W;
	S[N++] = X;
	X += T - X % T;
	for(int i = 0; i < M; i++) die[i] = X / T;
	ans += X / T * W;

	//for(int i = 0; i < M; i++) printf("(%lld, %lld)", DC[i].first, DC[i].second);
	//printf("\nX = %lld\n", X);

	//printf("ans = %lld\n", ans);
	for(int i = 0; i < N; i++) {
		int t = M - 1;
		while(t >= 0 && DC[t].first > S[i] % T) t--;
		//printf("t = %d\n", t);
		if(t == -1) break;
		while(t >= 0 && die[t] > S[i] / T) t--;
		//printf("t = %d\n", t);
		lint s = 0ll, mx = 0ll;
		int mxidx = t;
		for(t++; t < M && DC[t].first <= S[i] % T; t++) {
			s -= (die[t] - S[i] / T) * W;
			if(die[t] == X / T) s += DC[t].second;
			if(s > mx) {
				mx = s;
				mxidx = t;
			}
			//printf("t = %d, s = %lld, mx = %lld, mxidx = %d\n", t, s, mx, mxidx);
		}
		//printf("*\n");
		for(int j = mxidx + 1; j < M && DC[j].first < S[i] % T; j++) {
			//printf("j = %d\n", j);
			ans -= (die[j] - S[i] / T) * W;
			if(die[j] == X / T) ans += DC[j].second;
			die[j] = S[i] / T;
		}
		//printf("ans = %lld\n", ans);
	}

	printf("%lld", ans);
	return 0;
}

Compilation message

coach.cpp: In function 'int main()':
coach.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%d%d%lld%lld", &X, &N, &M, &W, &T);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
coach.cpp:21:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0; i < N; i++) scanf("%lld", S + i);
                             ~~~~~^~~~~~~~~~~~~~~
coach.cpp:22:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0; i < M; i++) scanf("%lld%lld", &DC[i].first, &DC[i].second);
                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -