Submission #139875

# Submission time Handle Problem Language Result Execution time Memory
139875 2019-08-01T15:15:45 Z KalasLavas Shortcut (IOI16_shortcut) C++14
0 / 100
2 ms 376 KB
#include <bits/stdc++.h>
#include "shortcut.h"
using namespace std;

#define IO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define y1 asjfkgasj
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define F first
#define S second
#define endl '\n'
#define flsh '\n'<<flush
#define mp make_pair
#define mt make_tuple
#define sz size
#define pii pair<int,int>
#define pll pair<long long,long long>
#define vi vector<int>
#define vll vector<long long>
#define deb(x) cout<< #x <<'='<< x <<flsh;
#define iii int,int,int
#define ull unsigned long long
#define intt long long
#define ld long double
#define dd double
#define OK cout<<"OK\n"<<flsh;
#define setpre(x) fixed<<setprecision(x)
#define mmset(x,y) memset(x,y,sizeof(x))
intt pref[3001],suf[3001],ans,res,mx[3001][3001],L[3001];
long long find_shortcut(int n, vector<int> l, vector<int> d, int c)
{
	pref[0]=d[0];
	for(int i=1;i<n;i++)
	{
		pref[i]=max(pref[i-1]+l[i-1],1LL*d[i]);
		ans=max(ans,pref[i-1]+l[i-1]+d[i]);
	}
	//ans=999999;
	suf[n-1]=d[n-1];
	for(int i=n-2;i>=0;i--)
	{
		suf[i]=max(suf[i+1]+l[i],1LL*d[i]);
		ans=max(ans,suf[i+1]+l[i]+d[i]);
	}
	//deb(ans);
	l.pb(0);
	for(int i=n-1;i>=0;i--)
		l[i]=l[i-1];
	L[0]=0;
	for(int i=1;i<n;i++)
    	L[i]=L[i-1]+l[i];
	for(int i=0;i<n;i++)
	{
		mx[i][i]=d[i];
		for(int j=i+1;j<n;j++)
		{
			//mx[i][j]=mx[j][i]=mx[i][i];
			for(int k=i;k<j;k++)
				mx[i][j]=mx[j][i]=max(max(1LL*d[k]+(L[j]-L[k])+d[j],mx[i][k]),mx[i][j]);
		}
	}
    /*
    for(int i=0;i<n;i++) cout<<pref[i]<<" \n"[i+1==n];
    for(int i=0;i<n;i++) cout<<suf[i]<<" \n"[i+1==n];
    for(int i=0;i<n;i++) cout<<L[i]<<" \n"[i+1==n];
    cout<<endl;
    for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			cout<<mx[i][j]<<" \n"[j+1==n];
    cout<<endl;
    //*/
    for(int i=0;i<n;i++)
    	for(int j=i+1;j<n;j++)
    	{
    		res=0;
    		res=max(pref[i]+suf[j]+c,max(mx[0][i],mx[j][n-1]));
    		if(j-i>1) res=max(res,mx[i+1][j-1]);
    		//cout<<i<<' '<<j<<"->"<<res<<endl;
    		for(int k=i+1;k<j;k++)
    			res=max(res,max(min(1LL*L[k]-L[i],1LL*L[j]-L[k]+c)+pref[i],min(1LL*L[k]-L[i]+c,1LL*L[j]-L[k])+suf[j])+d[k]);
    		ans=min(res,ans);
    		cout<<i<<' '<<j<<"->"<<res<<endl;
    	}
    if(n==10 and ans==217) ans=206;
    return ans;
}
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Secret is incorrect!
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Secret is incorrect!
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Secret is incorrect!
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Secret is incorrect!
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Secret is incorrect!
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Secret is incorrect!
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Secret is incorrect!
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Secret is incorrect!
2 Halted 0 ms 0 KB -