oj.uz

Submission #121532

# Submission time Handle Problem Language Result Execution time Memory
121532 2019-06-26T17:38:27 Z shayan_p Long Distance Coach (JOI17_coach) C++14
16 / 100
 5 ms 3584 KB 
// 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];
    }
    sort(a,a+n);
    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
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3584 KB Output is correct
2 Correct 4 ms 3456 KB Output is correct
3 Correct 5 ms 3456 KB Output is correct
4 Correct 4 ms 3456 KB Output is correct
5 Correct 4 ms 3456 KB Output is correct
6 Correct 5 ms 3456 KB Output is correct
7 Correct 4 ms 3456 KB Output is correct
8 Correct 5 ms 3456 KB Output is correct
9 Correct 4 ms 3456 KB Output is correct
10 Correct 4 ms 3456 KB Output is correct
11 Correct 5 ms 3456 KB Output is correct
12 Correct 4 ms 3584 KB Output is correct
13 Correct 5 ms 3456 KB Output is correct
14 Correct 5 ms 3556 KB Output is correct
15 Correct 5 ms 3456 KB Output is correct
16 Correct 5 ms 3456 KB Output is correct
17 Correct 5 ms 3584 KB Output is correct
18 Correct 5 ms 3456 KB Output is correct
19 Correct 4 ms 3456 KB Output is correct
20 Correct 4 ms 3556 KB Output is correct
21 Correct 5 ms 3456 KB Output is correct
22 Correct 4 ms 3456 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3584 KB Output is correct
2 Correct 4 ms 3456 KB Output is correct
3 Correct 5 ms 3456 KB Output is correct
4 Correct 4 ms 3456 KB Output is correct
5 Correct 4 ms 3456 KB Output is correct
6 Correct 5 ms 3456 KB Output is correct
7 Correct 4 ms 3456 KB Output is correct
8 Correct 5 ms 3456 KB Output is correct
9 Correct 4 ms 3456 KB Output is correct
10 Correct 4 ms 3456 KB Output is correct
11 Correct 5 ms 3456 KB Output is correct
12 Correct 4 ms 3584 KB Output is correct
13 Correct 5 ms 3456 KB Output is correct
14 Correct 5 ms 3556 KB Output is correct
15 Correct 5 ms 3456 KB Output is correct
16 Correct 5 ms 3456 KB Output is correct
17 Correct 5 ms 3584 KB Output is correct
18 Correct 5 ms 3456 KB Output is correct
19 Correct 4 ms 3456 KB Output is correct
20 Correct 4 ms 3556 KB Output is correct
21 Correct 5 ms 3456 KB Output is correct
22 Correct 4 ms 3456 KB Output is correct
23 Incorrect 5 ms 3456 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3584 KB Output is correct
2 Correct 4 ms 3456 KB Output is correct
3 Correct 5 ms 3456 KB Output is correct
4 Correct 4 ms 3456 KB Output is correct
5 Correct 4 ms 3456 KB Output is correct
6 Correct 5 ms 3456 KB Output is correct
7 Correct 4 ms 3456 KB Output is correct
8 Correct 5 ms 3456 KB Output is correct
9 Correct 4 ms 3456 KB Output is correct
10 Correct 4 ms 3456 KB Output is correct
11 Correct 5 ms 3456 KB Output is correct
12 Correct 4 ms 3584 KB Output is correct
13 Correct 5 ms 3456 KB Output is correct
14 Correct 5 ms 3556 KB Output is correct
15 Correct 5 ms 3456 KB Output is correct
16 Correct 5 ms 3456 KB Output is correct
17 Correct 5 ms 3584 KB Output is correct
18 Correct 5 ms 3456 KB Output is correct
19 Correct 4 ms 3456 KB Output is correct
20 Correct 4 ms 3556 KB Output is correct
21 Correct 5 ms 3456 KB Output is correct
22 Correct 4 ms 3456 KB Output is correct
23 Incorrect 5 ms 3456 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3584 KB Output is correct
2 Correct 4 ms 3456 KB Output is correct
3 Correct 5 ms 3456 KB Output is correct
4 Correct 4 ms 3456 KB Output is correct
5 Correct 4 ms 3456 KB Output is correct
6 Correct 5 ms 3456 KB Output is correct
7 Correct 4 ms 3456 KB Output is correct
8 Correct 5 ms 3456 KB Output is correct
9 Correct 4 ms 3456 KB Output is correct
10 Correct 4 ms 3456 KB Output is correct
11 Correct 5 ms 3456 KB Output is correct
12 Correct 4 ms 3584 KB Output is correct
13 Correct 5 ms 3456 KB Output is correct
14 Correct 5 ms 3556 KB Output is correct
15 Correct 5 ms 3456 KB Output is correct
16 Correct 5 ms 3456 KB Output is correct
17 Correct 5 ms 3584 KB Output is correct
18 Correct 5 ms 3456 KB Output is correct
19 Correct 4 ms 3456 KB Output is correct
20 Correct 4 ms 3556 KB Output is correct
21 Correct 5 ms 3456 KB Output is correct
22 Correct 4 ms 3456 KB Output is correct
23 Incorrect 5 ms 3456 KB Output isn't correct
24 Halted 0 ms 0 KB -