Submission #27478

#	Time	Username	Problem	Language	Result	Execution time	Memory
27478		tlwpdus	Long Distance Coach (JOI17_coach)	C++11	100 / 100	313 ms	23912 KiB

coach

#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;

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

struct wat {
	ll q, r, loc;
	bool operator < (const wat &A) const {return loc<A.loc;}
};

ll ccw(const pll &a,const pll &b,const pll &c) {return a.x*b.y+b.x*c.y+c.x*a.y-a.y*b.x-b.y*c.x-c.y*a.x;}
pll operator * (const pll &a, const pll &b) {return pll(a.second-b.second,b.first-a.first);}
bool operator < (const pll &a, const pll &b) {return a.first*b.second<b.first*a.second;}
struct CHT {
	vector<pll> vec;
	void add(ll x, ll y) {
		pll tmp = pll(x,y);
		while(!vec.empty()&&vec.back().first>x) vec.pop_back();
		while(vec.size()>=2&&ccw(vec[vec.size()-2],vec.back(),tmp)>=0) vec.pop_back();
		if (!vec.empty()&&vec.back().first==x) {
			if (vec.back().second<=y) vec.pop_back();
			else return;
		}
		vec.push_back(tmp);
	}
	ll getv(ll x) {
		pll tmp = pll(x,1);
		int s = 0, e = (int)vec.size()-2;
		while(s<=e) {
			int m = (s+e)>>1;
			if (tmp<vec[m]*vec[m+1]) e = m-1;
			else s = m+1;
		}
		return vec[s].first*x+vec[s].second;
	}
} cht;

ll x, n, m, w, t, res;
wat S[200100];
pll DC[200100];
ll ps[200100];
ll dp[200100];

int main() {
	int i;

	lo tx, tn, tm, tw, tt;
	scanf("%lld%lld%lld%lld%lld",&tx,&tn,&tm,&tw,&tt); ++tn;
	x=tx;n=tn;m=tm;w=tw;t=tt;
	for (i=0;i<n;i++) {
		lo ta; ll a;
		if (i!=n-1) {scanf("%lld",&ta); a=ta;}
		else a = x;
		S[i].q = w*(a/t); S[i].r = a%t;
	}
	for (i=0;i<m;i++) {
		lo x, y;
		scanf("%lld%lld",&x,&y);
		DC[i] = pll(x,y);
	}
	m++; DC[m-1] = pll(0,0);
	sort(DC,DC+m);
	for (i=0;i<n;i++) S[i].loc = upper_bound(DC,DC+m,pll(S[i].r,0))-DC;
	for (i=m-1;i>=0;i--) {
		ll cnt = (DC[i].first<x%t)?x/t+1:x/t;
		ps[i] = ps[i+1] + w*cnt-DC[i].second;
		res += w*cnt;
	}
	sort(S,S+n);

	int j; i = n-1;
	for (j=m-1;j>=0;j--) {
		while(i>=0&&S[i].loc>j) {
			cht.add(S[i].q,dp[S[i].loc]-ps[S[i].loc]-S[i].loc*S[i].q);
			i--;
		}
		dp[j] = max((i==n-1)?0:cht.getv(j)+ps[j],dp[j+1]);
	}
	printf("%lld\n",(lo)(res-dp[1]));

    return 0;
}

Compilation message (stderr)

coach.cpp: In function 'int main()':
coach.cpp:53:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld%lld%lld",&tx,&tn,&tm,&tw,&tt); ++tn;
                                                   ^
coach.cpp:57:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   if (i!=n-1) {scanf("%lld",&ta); a=ta;}
                                 ^
coach.cpp:63:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&x,&y);
                          ^

• Subtask 1: 16 / 16
• Subtask 2: 30 / 30
• Subtask 3: 25 / 25
• Subtask 4: 29 / 29