oj.uz

Submission #121528

# Submission time Handle Problem Language Result Execution time Memory
121528 2019-06-26T17:28:11 Z shayan_p Long Distance Coach (JOI17_coach) C++14
0 / 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];

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});
	lst=a[i];
    }
    
    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<<dp[m]+ans<<endl,0;
}
// Deathly mistakes:
//  * Read the problem curfully.
//  * Check maxn.c
//  * Overflows.

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3456 KB Output is correct
2 Correct 4 ms 3456 KB Output is correct
3 Correct 4 ms 3456 KB Output is correct
4 Correct 4 ms 3584 KB Output is correct
5 Correct 5 ms 3584 KB Output is correct
6 Incorrect 4 ms 3456 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3456 KB Output is correct
2 Correct 4 ms 3456 KB Output is correct
3 Correct 4 ms 3456 KB Output is correct
4 Correct 4 ms 3584 KB Output is correct
5 Correct 5 ms 3584 KB Output is correct
6 Incorrect 4 ms 3456 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3456 KB Output is correct
2 Correct 4 ms 3456 KB Output is correct
3 Correct 4 ms 3456 KB Output is correct
4 Correct 4 ms 3584 KB Output is correct
5 Correct 5 ms 3584 KB Output is correct
6 Incorrect 4 ms 3456 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3456 KB Output is correct
2 Correct 4 ms 3456 KB Output is correct
3 Correct 4 ms 3456 KB Output is correct
4 Correct 4 ms 3584 KB Output is correct
5 Correct 5 ms 3584 KB Output is correct
6 Incorrect 4 ms 3456 KB Output isn't correct
7 Halted 0 ms 0 KB -