#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 |
- |
