oj.uz

Submission #113166

# Submission time Handle Problem Language Result Execution time Memory
113166 2019-05-24T05:48:55 Z baluteshih Shortcut (IOI16_shortcut) C++14
0 / 100
 2 ms 384 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define pb push_back
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define F first
#define S second
#define ET cout << "\n"
#define MP make_pair
#define MEM(i,j) memset(i,j,sizeof i)
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const ll INF=1e18;
ll find_shortcut(int n,vector<int> l,vector<int> d, int c)
{
	ll mx=-INF,ans=0;
	vector<ll> sl(n,0),ldp(n,0),rdp(n,0),lf(n,0),rf(n,0),nd(n,0);
	for(int i=0;i<n;++i)
		nd[i]=d[i];
	for(int i=1;i<n;++i)
		sl[i]=sl[i-1]+l[i-1];
	for(int i=0;i<n;++i)
		ldp[i]=max((ll)d[i],sl[i]+mx),mx=max(mx,ldp[i]-sl[i]);
	for(int i=1;i<n;++i)
		lf[i]=max(lf[i-1],ldp[i-1]+d[i]+sl[i]-sl[i-1]);
	
	for(int i=n-1;i>=0;--i)
		rdp[i]=max((ll)d[i],mx-sl[i]),mx=max(mx,rdp[i]+sl[i]);
	for(int i=n-2;i>=0;--i)
		rf[i]=max(rf[i+1],rdp[i+1]+d[i]+sl[i+1]-sl[i]);
	
	ans=lf[n-1];
	for(int i=0;i<n;++i)
		for(int j=i+1;j<n;++j)
		{
			if(sl[j]-sl[i]<=c) continue;
			ll tmp=max(lf[i],rf[j]),mx2=-INF,cir=sl[j]-sl[i]+c;
			nd[i]=ldp[i],nd[j]=rdp[j];
			deque<int> dq;
			for(int k=i+1;k<=j;++k)
			{
				while(dq.size()&&nd[dq.back()]-sl[dq.back()]<=nd[k-1]-sl[k-1])
					dq.pop_back();
				dq.pb(k-1);
				while(dq.size()&&(sl[k]-sl[dq[0]])*2>=cir)
					mx2=max(mx2,sl[dq[0]]+nd[dq[0]]),dq.pop_front();
				if(dq.size()) tmp=max(tmp,sl[k]+nd[k]+nd[dq[0]]-sl[dq[0]]);
				tmp=max(tmp,mx2+cir-sl[k]+nd[k]);
			}
			ans=min(tmp,ans),nd[i]=d[i],nd[j]=d[j];
		}
	return ans;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB n = 4, 80 is a correct answer
2 Correct 2 ms 384 KB n = 9, 110 is a correct answer
3 Correct 2 ms 364 KB n = 4, 21 is a correct answer
4 Correct 2 ms 384 KB n = 3, 4 is a correct answer
5 Incorrect 2 ms 384 KB n = 2, incorrect answer: jury 62 vs contestant 63
6 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB n = 4, 80 is a correct answer
2 Correct 2 ms 384 KB n = 9, 110 is a correct answer
3 Correct 2 ms 364 KB n = 4, 21 is a correct answer
4 Correct 2 ms 384 KB n = 3, 4 is a correct answer
5 Incorrect 2 ms 384 KB n = 2, incorrect answer: jury 62 vs contestant 63
6 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB n = 4, 80 is a correct answer
2 Correct 2 ms 384 KB n = 9, 110 is a correct answer
3 Correct 2 ms 364 KB n = 4, 21 is a correct answer
4 Correct 2 ms 384 KB n = 3, 4 is a correct answer
5 Incorrect 2 ms 384 KB n = 2, incorrect answer: jury 62 vs contestant 63
6 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB n = 4, 80 is a correct answer
2 Correct 2 ms 384 KB n = 9, 110 is a correct answer
3 Correct 2 ms 364 KB n = 4, 21 is a correct answer
4 Correct 2 ms 384 KB n = 3, 4 is a correct answer
5 Incorrect 2 ms 384 KB n = 2, incorrect answer: jury 62 vs contestant 63
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB n = 4, 80 is a correct answer
2 Correct 2 ms 384 KB n = 9, 110 is a correct answer
3 Correct 2 ms 364 KB n = 4, 21 is a correct answer
4 Correct 2 ms 384 KB n = 3, 4 is a correct answer
5 Incorrect 2 ms 384 KB n = 2, incorrect answer: jury 62 vs contestant 63
6 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB n = 4, 80 is a correct answer
2 Correct 2 ms 384 KB n = 9, 110 is a correct answer
3 Correct 2 ms 364 KB n = 4, 21 is a correct answer
4 Correct 2 ms 384 KB n = 3, 4 is a correct answer
5 Incorrect 2 ms 384 KB n = 2, incorrect answer: jury 62 vs contestant 63
6 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB n = 4, 80 is a correct answer
2 Correct 2 ms 384 KB n = 9, 110 is a correct answer
3 Correct 2 ms 364 KB n = 4, 21 is a correct answer
4 Correct 2 ms 384 KB n = 3, 4 is a correct answer
5 Incorrect 2 ms 384 KB n = 2, incorrect answer: jury 62 vs contestant 63
6 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB n = 4, 80 is a correct answer
2 Correct 2 ms 384 KB n = 9, 110 is a correct answer
3 Correct 2 ms 364 KB n = 4, 21 is a correct answer
4 Correct 2 ms 384 KB n = 3, 4 is a correct answer
5 Incorrect 2 ms 384 KB n = 2, incorrect answer: jury 62 vs contestant 63
6 Halted 0 ms 0 KB -