Submission #122115

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
122115	2019-06-27T14:53:30 Z	shayan_p	Long Distance Coach (JOI17_coach)	C++14	71 / 100	18 ms	3200 KB

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=1e5+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.0 / 16.0

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

Subtask #2
30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	2 ms	384 KB	Output is correct
12	Correct	2 ms	384 KB	Output is correct
13	Correct	2 ms	384 KB	Output is correct
14	Correct	2 ms	384 KB	Output is correct
15	Correct	2 ms	384 KB	Output is correct
16	Correct	2 ms	384 KB	Output is correct
17	Correct	2 ms	384 KB	Output is correct
18	Correct	2 ms	384 KB	Output is correct
19	Correct	2 ms	384 KB	Output is correct
20	Correct	2 ms	384 KB	Output is correct
21	Correct	2 ms	384 KB	Output is correct
22	Correct	2 ms	384 KB	Output is correct
23	Correct	2 ms	384 KB	Output is correct
24	Correct	2 ms	384 KB	Output is correct
25	Correct	2 ms	384 KB	Output is correct
26	Correct	2 ms	384 KB	Output is correct
27	Correct	2 ms	384 KB	Output is correct
28	Correct	2 ms	384 KB	Output is correct
29	Correct	2 ms	384 KB	Output is correct
30	Correct	2 ms	384 KB	Output is correct
31	Correct	2 ms	384 KB	Output is correct
32	Correct	2 ms	384 KB	Output is correct
33	Correct	2 ms	384 KB	Output is correct
34	Correct	2 ms	384 KB	Output is correct
35	Correct	3 ms	384 KB	Output is correct
36	Correct	2 ms	384 KB	Output is correct
37	Correct	3 ms	384 KB	Output is correct

Subtask #3
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	2 ms	384 KB	Output is correct
12	Correct	2 ms	384 KB	Output is correct
13	Correct	2 ms	384 KB	Output is correct
14	Correct	2 ms	384 KB	Output is correct
15	Correct	2 ms	384 KB	Output is correct
16	Correct	2 ms	384 KB	Output is correct
17	Correct	2 ms	384 KB	Output is correct
18	Correct	2 ms	384 KB	Output is correct
19	Correct	2 ms	384 KB	Output is correct
20	Correct	2 ms	384 KB	Output is correct
21	Correct	2 ms	384 KB	Output is correct
22	Correct	2 ms	384 KB	Output is correct
23	Correct	2 ms	384 KB	Output is correct
24	Correct	2 ms	384 KB	Output is correct
25	Correct	2 ms	384 KB	Output is correct
26	Correct	2 ms	384 KB	Output is correct
27	Correct	2 ms	384 KB	Output is correct
28	Correct	2 ms	384 KB	Output is correct
29	Correct	2 ms	384 KB	Output is correct
30	Correct	2 ms	384 KB	Output is correct
31	Correct	2 ms	384 KB	Output is correct
32	Correct	2 ms	384 KB	Output is correct
33	Correct	2 ms	384 KB	Output is correct
34	Correct	2 ms	384 KB	Output is correct
35	Correct	3 ms	384 KB	Output is correct
36	Correct	2 ms	384 KB	Output is correct
37	Correct	3 ms	384 KB	Output is correct
38	Correct	4 ms	512 KB	Output is correct
39	Correct	4 ms	444 KB	Output is correct
40	Correct	4 ms	512 KB	Output is correct
41	Correct	4 ms	512 KB	Output is correct
42	Correct	5 ms	512 KB	Output is correct
43	Correct	4 ms	512 KB	Output is correct
44	Correct	4 ms	512 KB	Output is correct
45	Correct	4 ms	512 KB	Output is correct
46	Correct	4 ms	640 KB	Output is correct
47	Correct	4 ms	512 KB	Output is correct
48	Correct	4 ms	512 KB	Output is correct
49	Correct	4 ms	512 KB	Output is correct
50	Correct	4 ms	512 KB	Output is correct
51	Correct	4 ms	512 KB	Output is correct

Subtask #4
0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	2 ms	384 KB	Output is correct
12	Correct	2 ms	384 KB	Output is correct
13	Correct	2 ms	384 KB	Output is correct
14	Correct	2 ms	384 KB	Output is correct
15	Correct	2 ms	384 KB	Output is correct
16	Correct	2 ms	384 KB	Output is correct
17	Correct	2 ms	384 KB	Output is correct
18	Correct	2 ms	384 KB	Output is correct
19	Correct	2 ms	384 KB	Output is correct
20	Correct	2 ms	384 KB	Output is correct
21	Correct	2 ms	384 KB	Output is correct
22	Correct	2 ms	384 KB	Output is correct
23	Correct	2 ms	384 KB	Output is correct
24	Correct	2 ms	384 KB	Output is correct
25	Correct	2 ms	384 KB	Output is correct
26	Correct	2 ms	384 KB	Output is correct
27	Correct	2 ms	384 KB	Output is correct
28	Correct	2 ms	384 KB	Output is correct
29	Correct	2 ms	384 KB	Output is correct
30	Correct	2 ms	384 KB	Output is correct
31	Correct	2 ms	384 KB	Output is correct
32	Correct	2 ms	384 KB	Output is correct
33	Correct	2 ms	384 KB	Output is correct
34	Correct	2 ms	384 KB	Output is correct
35	Correct	3 ms	384 KB	Output is correct
36	Correct	2 ms	384 KB	Output is correct
37	Correct	3 ms	384 KB	Output is correct
38	Correct	4 ms	512 KB	Output is correct
39	Correct	4 ms	444 KB	Output is correct
40	Correct	4 ms	512 KB	Output is correct
41	Correct	4 ms	512 KB	Output is correct
42	Correct	5 ms	512 KB	Output is correct
43	Correct	4 ms	512 KB	Output is correct
44	Correct	4 ms	512 KB	Output is correct
45	Correct	4 ms	512 KB	Output is correct
46	Correct	4 ms	640 KB	Output is correct
47	Correct	4 ms	512 KB	Output is correct
48	Correct	4 ms	512 KB	Output is correct
49	Correct	4 ms	512 KB	Output is correct
50	Correct	4 ms	512 KB	Output is correct
51	Correct	4 ms	512 KB	Output is correct
52	Runtime error	18 ms	3200 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
53	Halted	0 ms	0 KB	-

Submission #122115

Compilation message

Subtask #1 16.0 / 16.0

Subtask #2 30.0 / 30.0

Subtask #3 25.0 / 25.0

Subtask #4 0 / 29.0

Subtask #1
16.0 / 16.0

Subtask #2
30.0 / 30.0

Subtask #3
25.0 / 25.0

Subtask #4
0 / 29.0