oj.uz

Submission #27474

# Submission time Handle Problem Language Result Execution time Memory
27474 2017-07-13T06:09:51 Z 시제연(#1156) Long Distance Coach (JOI17_coach) C++
0 / 100
 3 ms 23912 KB 
#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);
		if (!vec.empty()&&vec.back().first>x) vec.clear();
		while(vec.size()>=2&&ccw(vec[vec.size()-2],vec.back(),tmp)>=0) vec.pop_back();
		if (vec.empty()||(vec.back().first!=x)) 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

coach.cpp: In function 'int main()':
coach.cpp:49: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:53: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:59: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
0 / 16.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 25.0

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

Subtask #4
0 / 29.0

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