oj.uz

답안 #27473

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
27473 2017-07-13T06:04:45 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 long double ll;
typedef pair<ll,ll> pll;

struct wat {
	ll q, r; lo 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 w, res; lo x, t, n, m;
wat S[200100];
pll DC[200100];
ll ps[200100];
ll dp[200100];

int main() {
	int i;

	scanf("%lld%lld%lld%Lf%lld",&x,&n,&m,&w,&t); ++n;
	for (i=0;i<n;i++) {
		lo a;
		if (i!=n-1) scanf("%lld",&a);
		else a = x;
		S[i].q = w*(a/t); S[i].r = a%t;
	}
	for (i=0;i<m;i++) scanf("%Lf%Lf",&DC[i].first,&DC[i].second);
	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",(long long)(res-dp[1]+0.5));

    return 0;
}

Compilation message

coach.cpp: In function 'int main()':
coach.cpp:48:45: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld%Lf%lld",&x,&n,&m,&w,&t); ++n;
                                             ^
coach.cpp:51:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   if (i!=n-1) scanf("%lld",&a);
                               ^
coach.cpp:55:62: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i=0;i<m;i++) scanf("%Lf%Lf",&DC[i].first,&DC[i].second);
                                                              ^

Subtask #1
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 23912 KB Output is correct
2 Correct 0 ms 23912 KB Output is correct
3 Correct 3 ms 23912 KB Output is correct
4 Correct 3 ms 23912 KB Output is correct
5 Correct 3 ms 23912 KB Output is correct
6 Correct 3 ms 23912 KB Output is correct
7 Correct 0 ms 23912 KB Output is correct
8 Incorrect 0 ms 23912 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 23912 KB Output is correct
2 Correct 0 ms 23912 KB Output is correct
3 Correct 3 ms 23912 KB Output is correct
4 Correct 3 ms 23912 KB Output is correct
5 Correct 3 ms 23912 KB Output is correct
6 Correct 3 ms 23912 KB Output is correct
7 Correct 0 ms 23912 KB Output is correct
8 Incorrect 0 ms 23912 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 23912 KB Output is correct
2 Correct 0 ms 23912 KB Output is correct
3 Correct 3 ms 23912 KB Output is correct
4 Correct 3 ms 23912 KB Output is correct
5 Correct 3 ms 23912 KB Output is correct
6 Correct 3 ms 23912 KB Output is correct
7 Correct 0 ms 23912 KB Output is correct
8 Incorrect 0 ms 23912 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 23912 KB Output is correct
2 Correct 0 ms 23912 KB Output is correct
3 Correct 3 ms 23912 KB Output is correct
4 Correct 3 ms 23912 KB Output is correct
5 Correct 3 ms 23912 KB Output is correct
6 Correct 3 ms 23912 KB Output is correct
7 Correct 0 ms 23912 KB Output is correct
8 Incorrect 0 ms 23912 KB Output isn't correct
9 Halted 0 ms 0 KB -