oj.uz

Submission #351981

# Submission time Handle Problem Language Result Execution time Memory
351981 2021-01-20T10:21:58 Z amunduzbaev Shortcut (IOI16_shortcut) C++14
0 / 100
 1 ms 364 KB 
#include "shortcut.h"
#include <bits/stdc++.h>

#ifndef EVAL
#include "grader.cpp"
#endif

using namespace std;
 
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define ll long long
//#define int long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define fastios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vll vector<ll>
#define vii vector<int>
#define vpii vector<pii>
#define vpll vector<pll>
#define cnt(a)__builtin_popcount(a)
template<class T> bool umin(T& a, const T& b) {return a > b? a = b, true:false;}
template<class T> bool umax(T& a, const T& b) {return a < b? a = b, true:false;}
 
const int N = 2e3+5;
const int mod = 1e9+7;
const ll inf = 1e18;
const ld Pi = acos(-1);

ll pref[N], suf[N];
ll ans;
ll dd[N];



ll find_shortcut(int n, vector<int> l, vector<int> d, int c){
	int dis = 0;
	for(int i=0;i<n;i++){
		pref[i] = max(d[i], dis);
		if(i < n-1) dis = pref[i] + l[i];
		if(i) dd[i] = dd[i-1] + l[i-1];
	}
	dis = 0;
	for(int i=n-1;i>=0;i--){
		suf[i] = max(d[i], dis);
		if(i > 0) dis = suf[i] + l[i-1];
	}
	ll diam = 0;
	for(int i=0;i<n;i++) diam = max(diam, pref[i] + suf[i]);
	
	//for(int i=0;i<n;i++) cout<<pref[i]<<" ";
	//cout<<"\n";
	//for(int i=0;i<n;i++) cout<<suf[i]<<" ";
	//cout<<"\n";
	
	ans = diam;
	//cout<<diam<<"\n";
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			diam = pref[i] + suf[j] + c;
			ll dis = dd[j] - dd[i];
			//cout<<diam<<"\n";
			for(int l=0;l<=i;l++) diam = max(diam, pref[l] + suf[l] - dis + c);
			{
				vector<ll> tp(n, 0), ts(n, 0);
				ll dds = 0;
				for(int k=0;k<j;k++){
					tp[k] = max((ll)d[k], dds);
					dds = tp[k] + l[k];
					
				}dds = 0;
				for(int k = j-1;k>=0;k--){
					ts[k] = max((ll)d[k], dds);
					if(k) dds = ts[k] + l[k-1];
				}
				//for(int k=0;k<n;k++) cout<<tp[k]<<" ";
				//cout<<"\n";
				//for(int k=0;k<n;k++) cout<<ts[k]<<" ";
				//cout<<"\n";
				for(int k=0;k<n;k++) diam = max(diam, tp[k] + ts[k]);
				
				tp.assign(n, 0);
				ts.assign(n, 0);
				dds = 0;
				for(int k=i+1;k<n;k++){
					tp[k] = max((ll)d[k], dds);
					if(k < n-1) dds = tp[k] + l[k];
				}dds = 0;
				for(int k = n-1;k>i;k--){
					ts[k] = max((ll)d[k], dds);
					dds = ts[k] + l[k-1];
				}
				//for(int k=0;k<n;k++) cout<<tp[k]<<" ";
				//cout<<"\n";
				//for(int k=0;k<n;k++) cout<<ts[k]<<" ";
				//cout<<"\n";
				
				for(int k=0;k<n;k++) diam = max(diam, tp[k] + ts[k]);
				
				tp.assign(n, 0);
				ts.assign(n, 0);
				dds = 0;
				for(int k=i+1;k<j;k++){
					tp[k] = max((ll)d[k], dds);
					dds = tp[k] + l[k];
				}dds = 0;
				for(int k = j-1;k>i;k--){
					ts[k] = max((ll)d[k], dds);
					dds = ts[k] + l[k-1];
				}
				//for(int k=0;k<n;k++) cout<<tp[k]<<" ";
				//cout<<"\n";
				//for(int k=0;k<n;k++) cout<<ts[k]<<" ";
				//cout<<"\n";
				for(int k=0;k<n;k++) diam = max(diam, tp[k] + ts[k]);
				
			}
			for(int l=j;l<n;l++) diam = max(diam, pref[l] + suf[l] - dis + c);
			
			//cout<<dis<<" "<<i<<" "<<j<<" "<<diam<<"\n______\n";
			ans = min(ans, diam);
		}
	}
    return ans;
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 7.0

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

Subtask #5
0 / 33.0

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

Subtask #6
0 / 22.0

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

Subtask #7
0 / 4.0

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

Subtask #8
0 / 3.0

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