Submission #122116

#	Time	Username	Problem	Language	Result	Execution time	Memory
122116		shayan_p	Long Distance Coach (JOI17_coach)	C++14	100 / 100	363 ms	19944 KiB

coach

// High above the clouds there is a rainbow...

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;

const int maxn=2e5+10,mod=1e9+7;
const ll inf=1e18;

ll a[maxn],sm[maxn],dp[maxn];
pll b[maxn],p[maxn];
int bf[maxn];

vector<pll>v;

inline bool bad(pll a,pll b,pll c){
    return ld(a.S-b.S) / ld(a.F-b.F) <= ld(b.S-c.S) / ld(b.F-c.F);
}
inline ll get(pll p,ll x){
    return p.F*x + p.S;
}
void add(ll a,ll b){
    if(sz(v) && v.back().F == a){
	if(v.back().S <= b) return;
	v.pop_back();
    }
    while(sz(v) && bad(v[sz(v)-2], v[sz(v)-1], {a,b} ) ) v.pop_back();
    v.PB({a,b});
}
ll ask(ll x){
    assert(sz(v));
    int l=0,r=sz(v);
    while(r-l>2){
	int mid=(l+r+1)>>1;
	if(get(v[mid-1], x) < get(v[mid],x) ) r=mid;
	else l=mid;
    }
    if(r-l==1) return get(v[l],x);
    return min( get(v[l],x), get(v[l+1],x) );
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);

    int N,m; ll X,W,T; cin>>X>>N>>m>>W>>T;

    for(int i=0;i<N;i++)
	cin>>a[i];
    a[N++]=X;
    a[N++]=0;
    
    sort(a,a+N, [&](ll a,ll b){ if( (a%T)!=(b%T) ) return (a%T) < (b%T);  return a<b; } );

    int n=0;
    for(int i=0;i<N;i++){
	if(i==0 || (a[i]%T)!=(a[i-1]%T))
	    b[n++]= { a[i]%T, W*(a[i]/T) };
    }

    ll tot=W* ((X/T)+1);
    
    for(int i=0;i<m;i++){
	cin>>p[i].F>>p[i].S;
	ll num= (X/T) + (p[i].F < (X%T));
	p[i].S-= W* num;
	tot+= W* num;
    }
    sort(p,p+m);

    for(int i=0;i<m;i++){
	bf[i]= lower_bound(b,b+n, (pll){p[i].F,-1})-b-1;
	sm[i]= (i==0 ? 0 : sm[i-1] + p[i-1].S );
    }

    int pt=0,Cnt=0;
    ll SM=0;
    
    for(int i=1;i<n;i++){
	while(pt<m && p[pt].F<b[i].F) add(-pt, -sm[pt] + dp[bf[pt]] ), Cnt++, SM+=p[pt].S, pt++;
	dp[i]=dp[i-1];
	if(pt!=0) dp[i]= min(dp[i],  SM + Cnt * b[i].S + ask(b[i].S) );
    }
    return cout<<tot+dp[n-1]<<endl,0;
}
// Deathly mistakes:
//  * Read the problem curfully.
//  * Check maxn.
//  * Overflows.

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