제출 #121531

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
121531		shayan_p	Long Distance Coach (JOI17_coach)	C++14	0 / 100	4 ms	3456 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;

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

ll a[maxn], d[maxn], dp[maxn], W, T;
pll p[maxn];
vector<pair<int,ll> >vec[maxn];


vector< pair<pii,ll> > vv;



ll val[maxn];
void add(int l,int r,ll x){
    while(l<r)
	val[l]=min(val[l],x), l++;
}
ll ask(int pos){
    return val[pos];
}

int main(){
    fill(val,val+maxn,inf);

    ios_base::sync_with_stdio(false);cin.tie(0);

    ll x; int n,m; cin>>x>>n>>m>>W>>T;

    for(int i=0;i<n;i++){
	cin>>a[i];
    }
    a[n++]=x;

    ll ans=W*((x/T)+1);
    
    for(int i=0;i<m;i++){
	cin>>p[i].F>>p[i].S;
	d[i]=p[i].F;
	p[i].S-= W* (x/T), ans+= W* (x/T);
	if( (p[i].F%T) < (x%T) ) p[i].S-= W, ans+=W;
    }
    sort(p,p+m), sort(d,d+m);
    
    ll lst=0;
    for(int i=0;i<n;i++){
	int A=lower_bound(d,d+m,lst %T)-d, B=lower_bound(d,d+m,a[i] %T)-d;
	
	if( lst< (a[i]/T)*T ) lst= (a[i]/T)*T;
	A=lower_bound(d,d+m, lst%T)-d;

	assert(A<=B);
	
	if(A!=B) vec[B].PB({A,lst/T}), vv.PB({ {A,B}, lst/T} );
	lst=a[i];
    }

    ll Ans=0;
    
    for(int msk=0;msk<(1<<m);msk++){
	ll num=0;
	for(int i=0;i<m;i++){
	    if(bit(msk,i)) continue;
	    num+= p[i].S;
	    ll can=inf;
	    for(auto it:vv){
		if( it.F.F<=i && i<it.F.S ){
		    bool ok=1;
		    for(int j=i;j<it.F.S;j++)
			ok&= bit(msk,j)==0;
		    if(ok) can= min(can, it.S);
		}
	    }
	    if(can==inf) goto Hell;
	    num+= W*can;
	}
	Ans=min(Ans,num);
    Hell:;
    }
    /*
    for(int i=0;i<=m;i++){
	for(auto p:vec[i])
	    add(p.F,i, p.S);
	dp[i]=0;
	ll num=0;
	for(int j=i-1;j>=0;j--){
	    dp[i]= min(dp[i], num+dp[j]);
	    if(ask(j)==inf) goto Hell;
	    num+= p[j].S + W*ask(j);
	}
	dp[i]= min( dp[i], num);
    Hell:;
    }*/
    return cout<<Ans+ans<<endl,0;
}
// Deathly mistakes:
//  * Read the problem curfully.
//  * Check maxn.c
//  * Overflows.

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