Submission #27668

#	Time	Username	Problem	Language	Result	Execution time	Memory
27668		suhgyuho_william	Long Distance Coach (JOI17_coach)	C++14	71 / 100	2000 ms	11396 KiB

coach

#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;
lld a[200002],d[200002],memo[200002],sum[200002];
struct data{
	lld d,c;
	data(){}
	data(lld d,lld c):d(d),c(c){}
	bool operator < (const data &cmp) const{
		return d < cmp.d;
	}
}b[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);
	for(int i=1; i<=M; i++){
		long long id,ic;
		scanf("%lld %lld",&id,&ic);
		b[i].d = id; b[i].c = ic;
	}
	sort(b+1,b+M+1);
	a[N+1] = X;
	for(int i=1; i<=M; i++){
		memo[i] = Linf;
		sum[i] = sum[i-1]+b[i].c;
	}
	for(int i=1; i<=N+1; i++){
		int it;
		it = lower_bound(b+1,b+M+1,data(a[i]%T,0))-b-1;
		memo[it] = min(memo[it],a[i]/T);
	}
	d[0] = get(0);
	for(int i=1; i<=M; i++){
		d[i] = d[i-1]+get(b[i].d);
		if(memo[i] == Linf) continue;
		for(int j=0; j<i; j++){
			d[i] = min(d[i],d[j]+sum[i]-sum[j]+W*(i-j)*memo[i]);
		}
	}
	long long print = d[M];
	printf("%lld\n",print);

	return 0;
}

Compilation message (stderr)

coach.cpp: In function 'int main()':
coach.cpp:32: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:36:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&ia);
                    ^
coach.cpp:42: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: 16 / 16
• Subtask 2: 30 / 30
• Subtask 3: 25 / 25
• Subtask 4: 0 / 29