oj.uz

답안 #27480

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
27480 2017-07-13T07:02:13 Z 서규호(#1154) Long Distance Coach (JOI17_coach) C++14
0 / 100
 0 ms 6904 KB 
#include <bits/stdc++.h>

#define lld long long
#define pii pair<int,int>
#define pll pair<lld,lld>
#define pb push_back
#define next nextt
#define Inf 1000000000
#define Linf 1000000000000000000LL
#define Mod 1000000007

using namespace std;

int N,M;
lld X,W,T,ans;
lld a[200002];
struct data{
	lld d,c;
}b[200002];
bool check[200002];

lld get(lld x){
	return ((X-x)/T+1)*W;
}

int main(){
	scanf("%lld %d %d %lld %lld",&X,&N,&M,&W,&T);
	for(int i=1; i<=N; i++){
		scanf("%lld",&a[i]);
	}
	sort(a+1,a+N+1);
	ans += get(0);
	for(int i=1; i<=M; i++){
		scanf("%lld %lld",&b[i].d,&b[i].c);
		ans += get(b[i].d);
	}
	sort(b+1,b+M+1,[&](data &x,data &y){
		return x.d < y.d;
	});
	a[N+1] = X;
	for(int i=1; i<=N+1; i++){
		lld s,e;
		s = max(a[i-1],(a[i]/T)*T)+1;
		e = a[i]-1;
		if(s > e) continue;
		s %= T; e %= T;
		if(e < b[1].d || b[M].d < s) continue;
		int it1,it2,l,r;
		l = 1; r = M;
		while(l <= r){
			int m = (l+r)>>1;
			if(b[m].d >= s){
				it1 = m;
				r = m-1;
			}else l = m+1;
		}
		l = 1; r = M;
		while(l <= r){
			int m = (l+r)>>1;
			if(b[m].d <= e){
				it2 = m;
				l = m+1;
			}else r = m-1;
		}
		if(it1 > it2) continue;
		int it;
		lld small = 0,sum = 0;
		for(int j=it2; j>=it1; j--){
			if(check[j]) continue;
			sum += b[j].c;
			sum -= get((a[i]/T)*T+b[j].d);
			if(small > sum){
				small = sum;
				it = j;
			}
		}
		if(small == 0) continue;
		ans += small;
		for(int j=it2; j>=it; j--) check[j] = true;
	}
	printf("%lld\n",ans);

	return 0;
}

Compilation message

coach.cpp: In function 'int main()':
coach.cpp:27:46: 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:29:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&a[i]);
                      ^
coach.cpp:34:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld",&b[i].d,&b[i].c);
                                     ^
coach.cpp:68:3: warning: 'it' may be used uninitialized in this function [-Wmaybe-uninitialized]
   for(int j=it2; j>=it1; j--){
   ^
coach.cpp:68:19: warning: 'it1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   for(int j=it2; j>=it1; j--){
                   ^

Subtask #1
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 6904 KB Output is correct
2 Correct 0 ms 6904 KB Output is correct
3 Correct 0 ms 6904 KB Output is correct
4 Correct 0 ms 6904 KB Output is correct
5 Correct 0 ms 6904 KB Output is correct
6 Correct 0 ms 6904 KB Output is correct
7 Correct 0 ms 6904 KB Output is correct
8 Correct 0 ms 6904 KB Output is correct
9 Correct 0 ms 6904 KB Output is correct
10 Correct 0 ms 6904 KB Output is correct
11 Correct 0 ms 6904 KB Output is correct
12 Correct 0 ms 6904 KB Output is correct
13 Correct 0 ms 6904 KB Output is correct
14 Correct 0 ms 6904 KB Output is correct
15 Correct 0 ms 6904 KB Output is correct
16 Correct 0 ms 6904 KB Output is correct
17 Correct 0 ms 6904 KB Output is correct
18 Correct 0 ms 6904 KB Output is correct
19 Correct 0 ms 6904 KB Output is correct
20 Correct 0 ms 6904 KB Output is correct
21 Incorrect 0 ms 6904 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 6904 KB Output is correct
2 Correct 0 ms 6904 KB Output is correct
3 Correct 0 ms 6904 KB Output is correct
4 Correct 0 ms 6904 KB Output is correct
5 Correct 0 ms 6904 KB Output is correct
6 Correct 0 ms 6904 KB Output is correct
7 Correct 0 ms 6904 KB Output is correct
8 Correct 0 ms 6904 KB Output is correct
9 Correct 0 ms 6904 KB Output is correct
10 Correct 0 ms 6904 KB Output is correct
11 Correct 0 ms 6904 KB Output is correct
12 Correct 0 ms 6904 KB Output is correct
13 Correct 0 ms 6904 KB Output is correct
14 Correct 0 ms 6904 KB Output is correct
15 Correct 0 ms 6904 KB Output is correct
16 Correct 0 ms 6904 KB Output is correct
17 Correct 0 ms 6904 KB Output is correct
18 Correct 0 ms 6904 KB Output is correct
19 Correct 0 ms 6904 KB Output is correct
20 Correct 0 ms 6904 KB Output is correct
21 Incorrect 0 ms 6904 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 6904 KB Output is correct
2 Correct 0 ms 6904 KB Output is correct
3 Correct 0 ms 6904 KB Output is correct
4 Correct 0 ms 6904 KB Output is correct
5 Correct 0 ms 6904 KB Output is correct
6 Correct 0 ms 6904 KB Output is correct
7 Correct 0 ms 6904 KB Output is correct
8 Correct 0 ms 6904 KB Output is correct
9 Correct 0 ms 6904 KB Output is correct
10 Correct 0 ms 6904 KB Output is correct
11 Correct 0 ms 6904 KB Output is correct
12 Correct 0 ms 6904 KB Output is correct
13 Correct 0 ms 6904 KB Output is correct
14 Correct 0 ms 6904 KB Output is correct
15 Correct 0 ms 6904 KB Output is correct
16 Correct 0 ms 6904 KB Output is correct
17 Correct 0 ms 6904 KB Output is correct
18 Correct 0 ms 6904 KB Output is correct
19 Correct 0 ms 6904 KB Output is correct
20 Correct 0 ms 6904 KB Output is correct
21 Incorrect 0 ms 6904 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 6904 KB Output is correct
2 Correct 0 ms 6904 KB Output is correct
3 Correct 0 ms 6904 KB Output is correct
4 Correct 0 ms 6904 KB Output is correct
5 Correct 0 ms 6904 KB Output is correct
6 Correct 0 ms 6904 KB Output is correct
7 Correct 0 ms 6904 KB Output is correct
8 Correct 0 ms 6904 KB Output is correct
9 Correct 0 ms 6904 KB Output is correct
10 Correct 0 ms 6904 KB Output is correct
11 Correct 0 ms 6904 KB Output is correct
12 Correct 0 ms 6904 KB Output is correct
13 Correct 0 ms 6904 KB Output is correct
14 Correct 0 ms 6904 KB Output is correct
15 Correct 0 ms 6904 KB Output is correct
16 Correct 0 ms 6904 KB Output is correct
17 Correct 0 ms 6904 KB Output is correct
18 Correct 0 ms 6904 KB Output is correct
19 Correct 0 ms 6904 KB Output is correct
20 Correct 0 ms 6904 KB Output is correct
21 Incorrect 0 ms 6904 KB Output isn't correct
22 Halted 0 ms 0 KB -