Submission #1245147

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245147		Saul0906	Shortcut (IOI16_shortcut)	C++20	0 / 100	1 ms	328 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define rep(a,b,c) for(int a=b; a<c; a++)
#define repr(a,b,c) for(int a=b-1; a>c-1; a--)
#define repa(a,b) for(auto a:b)
#define ll long long
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define pii pair<int, int>
#define fi first
#define se second
#define mid ((l+r)>>1)

using namespace std;
using vi = vector<int>;

const ll inf=1e18;

const int N=2e5+5;
ll dis[N], rdis[N], sp[20][N], rsp[20][N];

ll query(int l, int r, bool z){
	if(l>r) return -inf;
	ll k=__lg(r-l+1), x=1<<k;
	if(z) return max(rsp[k][l],rsp[k][r-x+1]);
	else return max(sp[k][l],sp[k][r-x+1]);
}

long long find_shortcut(int n, vector<int> l, vector<int> d, int c){
	ll dp[n+5][n+5]{};
	dis[0]=rdis[n-1]=0;
	repr(i,n-1,0) rdis[i]=rdis[i+1]+l[i];
	rep(i,1,n) dis[i]=dis[i-1]+l[i-1];
	rep(i,0,n){
		sp[0][i]=dis[i]+d[i];
		rsp[0][i]=rdis[i]+d[i];
	}
	rep(j,1,20){
		rep(i,0,n){
			if(i+(1<<j)>n) continue;
			sp[j][i]=max(sp[j-1][i],sp[j-1][i+(1<<j-1)]);
			rsp[j][i]=max(rsp[j-1][i],rsp[j-1][i+(1<<j-1)]);
		}
	}
	rep(i,0,n) rep(j,i+1,n) dp[i][j]=max(dp[i][j],dis[j]-dis[i]+d[i]+d[j]);
	rep(i,0,n) rep(j,i,n){
		if(j<n) dp[i][j+1]=max(dp[i][j+1],dp[i][j]);
		if(i) dp[i-1][j]=max(dp[i-1][j],dp[i][j]);
	}
	ll ans=inf;
	rep(i,0,n){
		rep(j,i+1,n){
			ll v=0, ind=i;
			v=max(dp[0][i-1],dp[j+1][n-1]);
			v=max(v,query(0,i-1,1)+query(j+1,n-1,0)-dis[j]-rdis[i]+c);
			rep(k,i,j+1){
				while(ind<=j && dis[ind]-dis[k]<=dis[k]-dis[i]+dis[j]-dis[ind]+c) ind++;
				v=max(v,d[k]+query(k+1,ind-1,0)-dis[k]);
				v=max(v,d[k]+query(ind,j,1)+c+dis[k]-dis[i]-rdis[j]);
				if(ind>j) v=max(v,query(j,n-1,0)-dis[k]+d[k]);
				else v=max(v,query(j,n-1,0)-dis[j]+dis[k]-dis[i]+c+d[k]);
			}
			ind=j;
			repr(k,j+1,i){
				while(ind>=i && dis[k]-dis[ind]<=dis[j]-dis[k]+dis[ind]-dis[i]+c) ind--;
				if(ind<i) v=max(v,query(0,i,1)-rdis[k]+d[k]);
				else v=max(v,query(0,i,1)-rdis[i]+dis[j]-dis[k]+c+d[k]);
			}
			/*
			int l=i, r=j;
			while(l<=r){
				if(dis[mid]-dis[i]<=dis[r]-dis[mid]+c) l=mid+1;
				else r=mid-1;
			}
			v=max(v,query(0,i,1)+query(i,r,0)-dis[i]-rdis[i]);
			v=max(v,query(0,i,1)+query(l,j,1)+c-rdis[i]-rdis[j]);
			l=i, r=j;
			while(l<=r){
				if(dis[j]-dis[mid]<=dis[mid]-dis[i]+c) r=mid-1;
				else l=mid+1;
			}
			v=max(v,query(j,n-1,0)+query(l,j,1)-dis[j]-rdis[j]);
			v=max(v,query(j,n-1,0)+query(i,r,0)+c-dis[i]-dis[j]);
			*/
			ans=min(ans,v);
		}
	}
	return ans;
}

Compilation message (stderr)

shortcut.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
shortcut_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 14
• Subtask 3: 0 / 8
• Subtask 4: 0 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3