oj.uz

Submission #27627

# Submission time Handle Problem Language Result Execution time Memory
27627 2017-07-13T10:25:10 Z suhgyuho_william Long Distance Coach (JOI17_coach) C++14
0 / 100
 0 ms 39780 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;
int it1[200002],it2[200002];
lld X,W,T,ans;
lld a[200002],d[2002][2002];
struct data{
	lld d,c;
}b[200002];
bool check[200002];

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

int main(){
	long long iX,iW,iT;
	scanf("%lld %d %d %lld %lld",&iX,&N,&M,&iW,&iT);
	X = iX; W = iW; T = iT;
	for(int i=1; i<=N; i++){
		long long ia;
		scanf("%lld",&ia);
		a[i] = ia;
	}
	sort(a+1,a+N+1);
	ans += get(0);
	for(int i=1; i<=M; i++){
		long long id,ic;
		scanf("%lld %lld",&id,&ic);
		b[i].d = id; b[i].c = ic;
		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 l,r;
		l = 1; r = M;
		while(l <= r){
			int m = (l+r)>>1;
			if(b[m].d >= s){
				it1[i] = 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[i] = m;
				l = m+1;
			}else r = m-1;
		}
		if(it1[i] > it2[i]) continue;
	}
	for(int i=M; i>=1; i--){
		vector<pll> tmp;
		for(int j=1; j<=N+1; j++){
			if(it1[j] == 0 || it1[j] > it2[j]) continue;
			if(!(it1[j] <= i && i <= it2[j])) continue;
			tmp.pb({it2[j],b[i].c-get((a[j]/T)*T+b[i].d)});
		}
		sort(tmp.begin(),tmp.end());
		if(tmp.size() == 0) continue;
		int it = 0;
		lld ben = Linf;
		for(int j=i; j<=M; j++){
			while(it<tmp.size()){
				if(tmp[it].first > j) break;
				ben = min(ben,tmp[it].second);
				it++;
			}
			d[i][j] = d[i+1][j]+ben;
		}
		for(int j=i+1; j<=M; j++) d[i][0] = min(d[i][0],d[i+1][j]);
		d[i][0] = min(d[i][0],d[i+1][0]);
	}
	lld small = 0;
	for(int i=0; i<=M; i++) small = min(small,d[1][i]);
	ans += small;
	long long print = ans;
	printf("%lld\n",print);

	return 0;
}

Compilation message

coach.cpp: In function 'int main()':
coach.cpp:86:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(it<tmp.size()){
            ^
coach.cpp:29:49: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %d %d %lld %lld",&iX,&N,&M,&iW,&iT);
                                                 ^
coach.cpp:33:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&ia);
                    ^
coach.cpp:40:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld",&id,&ic);
                             ^

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 39780 KB Output is correct
2 Correct 0 ms 39780 KB Output is correct
3 Correct 0 ms 39780 KB Output is correct
4 Correct 0 ms 39780 KB Output is correct
5 Correct 0 ms 39780 KB Output is correct
6 Incorrect 0 ms 39780 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 39780 KB Output is correct
2 Correct 0 ms 39780 KB Output is correct
3 Correct 0 ms 39780 KB Output is correct
4 Correct 0 ms 39780 KB Output is correct
5 Correct 0 ms 39780 KB Output is correct
6 Incorrect 0 ms 39780 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 39780 KB Output is correct
2 Correct 0 ms 39780 KB Output is correct
3 Correct 0 ms 39780 KB Output is correct
4 Correct 0 ms 39780 KB Output is correct
5 Correct 0 ms 39780 KB Output is correct
6 Incorrect 0 ms 39780 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 39780 KB Output is correct
2 Correct 0 ms 39780 KB Output is correct
3 Correct 0 ms 39780 KB Output is correct
4 Correct 0 ms 39780 KB Output is correct
5 Correct 0 ms 39780 KB Output is correct
6 Incorrect 0 ms 39780 KB Output isn't correct
7 Halted 0 ms 0 KB -