#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long 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;
scanf("%lld%lld%lld%lld%lld",&x,&n,&m,&w,&t); ++n;
for (i=0;i<n;i++) {
ll 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("%lld%lld",&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",res-dp[1]);
return 0;
}
Compilation message
coach.cpp: In function 'int main()':
coach.cpp:47:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld%lld%lld",&x,&n,&m,&w,&t); ++n;
^
coach.cpp:50: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:54:64: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (i=0;i<m;i++) scanf("%lld%lld",&DC[i].first,&DC[i].second);
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
12964 KB |
Output is correct |
| 2 |
Correct |
0 ms |
12964 KB |
Output is correct |
| 3 |
Correct |
0 ms |
12964 KB |
Output is correct |
| 4 |
Correct |
0 ms |
12964 KB |
Output is correct |
| 5 |
Correct |
0 ms |
12964 KB |
Output is correct |
| 6 |
Correct |
0 ms |
12964 KB |
Output is correct |
| 7 |
Correct |
0 ms |
12964 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
12964 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
12964 KB |
Output is correct |
| 2 |
Correct |
0 ms |
12964 KB |
Output is correct |
| 3 |
Correct |
0 ms |
12964 KB |
Output is correct |
| 4 |
Correct |
0 ms |
12964 KB |
Output is correct |
| 5 |
Correct |
0 ms |
12964 KB |
Output is correct |
| 6 |
Correct |
0 ms |
12964 KB |
Output is correct |
| 7 |
Correct |
0 ms |
12964 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
12964 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
12964 KB |
Output is correct |
| 2 |
Correct |
0 ms |
12964 KB |
Output is correct |
| 3 |
Correct |
0 ms |
12964 KB |
Output is correct |
| 4 |
Correct |
0 ms |
12964 KB |
Output is correct |
| 5 |
Correct |
0 ms |
12964 KB |
Output is correct |
| 6 |
Correct |
0 ms |
12964 KB |
Output is correct |
| 7 |
Correct |
0 ms |
12964 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
12964 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
12964 KB |
Output is correct |
| 2 |
Correct |
0 ms |
12964 KB |
Output is correct |
| 3 |
Correct |
0 ms |
12964 KB |
Output is correct |
| 4 |
Correct |
0 ms |
12964 KB |
Output is correct |
| 5 |
Correct |
0 ms |
12964 KB |
Output is correct |
| 6 |
Correct |
0 ms |
12964 KB |
Output is correct |
| 7 |
Correct |
0 ms |
12964 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
12964 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
