Submission #205386

#TimeUsernameProblemLanguageResultExecution timeMemory
205386awlintqaaShortcut (IOI16_shortcut)C++14
0 / 100
6 ms632 KiB
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0) #include <bits/stdc++.h> using namespace std; #define sqr 200 #define mid (l+r)/2 #define pb push_back #define ppb pop_back #define fi first #define se second #define lb lower_bound #define ub upper_bound #define ins insert #define era erase #define C continue #define mem(dp,i) memset(dp,i,sizeof(dp)) #define mset multiset typedef long long ll; typedef short int si; typedef long double ld; typedef pair<int,int> pi; typedef pair<ll,ll> pll; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll; const ll mod=1e9+7; const ll inf= 4e18; const ld pai=acos(-1); #include "shortcut.h" ll n,cost; ll a[100009],d[100009]; ll dis(ll x,ll y){return abs(a[x]-a[y]);} ll solve(int x,int y){ if(dis(x,y)<cost)return inf; ll bef=0,aft=0; for(int i=0;i<=x;i++)bef=max(bef,dis(x,i)+d[i]); for(int i=y;i<n;i++) aft=max(aft,dis(y,i)+d[i]); ll ans=bef+aft+cost; for(int i=x+1;i<=y-1;i++){ ans=max(ans,bef+ min(dis(i,x),dis(i,y)+cost)+d[i]); ans=max(ans,aft+ min(dis(i,y),dis(i,x)+cost)+d[i]); } ll xxx=inf; for(int i=0;i<=x;i++){ ans=max(ans,a[i]+d[i]-xxx); xxx=min(xxx,a[i]-d[i]); }xxx=inf; for(int i=y;i<n;i++){ ans=max(ans,a[i]+d[i]-xxx); xxx=min(ans,a[i]-d[i]); } for(int i=x;i<=y;i++){ for(int j=i+1;j<=y;j++){ ans=max(ans,min(dis(i,j),dis(y,j)+dis(x,i)+cost)+d[i]+d[j]); } } return ans; } ll find_shortcut(int N, vi l, vi D, int c){ n=N;cost=c; for(int i=0;i<n;i++)d[i]=D[i]; for(int i=1;i<n;i++){ a[i]=a[i-1]+l[i-1]; } ll ans=0; for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ ans=max(ans,dis(i,j)+d[i]+d[j]); } } for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ ans=min(ans,solve(i,j)); } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...