제출 #278627

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
278627		eohomegrownapps	Shortcut (IOI16_shortcut)	C++14	31 / 100	2053 ms	39552 KiB

shortcut

    #include "shortcut.h"
    #include <bits/stdc++.h>
    using namespace std;
     
    typedef long long ll;
     
    ll find_shortcut(int n, vector<int> lv, vector<int> dv, int c){
    	ll l[1000000], d[1000000];
    	for (int i = 0; i<n-1; i++){
    		l[i]=lv[i];
    	}
    	for (int i = 0; i<n; i++){
    		d[i]=dv[i];
    	}
    	ll pathlength[1000000]={0};
    	pathlength[0]=0;
    	for (ll i = 1; i<n; i++){
    		pathlength[i]=pathlength[i-1]+l[i-1];
    	}
     
    	ll prefixmax[1000000]={0};
    	ll suffixmax[1000000]={0};
    	prefixmax[0]=pathlength[n-1]-pathlength[0]+d[0];
    	for (ll i = 1; i<n; i++){
    		prefixmax[i]=max(prefixmax[i-1],d[i]+pathlength[n-1]-pathlength[i]);
    	}
    	for (ll i = 0; i<n; i++){
    		prefixmax[i]-=pathlength[n-1]-pathlength[i];
    	}
    	suffixmax[n-1]=pathlength[n-1]-pathlength[0]+d[n-1];
    	for (ll i = n-2; i>=0; i--){
    		suffixmax[i]=max(suffixmax[i+1],d[i]+pathlength[i]-pathlength[0]);
    	}
    	for (ll i = 0; i<n; i++){
    		suffixmax[i]-=pathlength[i]-pathlength[0];
    	}
     
    	ll prefixrangemax[1000000]={0};
    	ll suffixrangemax[1000000]={0};
    	for (int i = 1; i<n; i++){
    		prefixrangemax[i]=prefixrangemax[i-1];
    		for (int j = 0; j<i; j++){
    			//from j to i
    			prefixrangemax[i]=max(prefixrangemax[i],d[i]+d[j]+pathlength[i]-pathlength[j]);
    		}
    	}
    	for (int i = n-2; i>=0; i--){
    		suffixrangemax[i]=suffixrangemax[i+1];
    		for (int j = i+1; j<n; j++){
    			//from j to i
    			suffixrangemax[i]=max(suffixrangemax[i],d[i]+d[j]+pathlength[j]-pathlength[i]);
    		}
    	}
     
    	ll endspluspath[1000000]={0};
    	ll endsminuspath[1000000]={0};
    	for (ll i = 0; i<n; i++){
    		endspluspath[i]=d[i]+pathlength[i];
    		endsminuspath[i]=d[i]-pathlength[i];
    	}
    	ll mindist = 1e18;
    	/*for (int i : prefixmax){
    		cout<<i<<' ';
    	}cout<<'\n';
    	for (int i : suffixmax){
    		cout<<i<<' ';
    	}cout<<'\n';*/
    	/*ll poss[1000000];
    	for (int i = 0; i<n; i++){
    		poss[i]=i;
    	}
    	std::random_device rd;
        std::mt19937 g(rd());
        shuffle(poss,poss+n,g);*/
    	//for (ll xv = 0; xv<n; xv++){
    	for (ll a = 0; a<n; a++){
    		//ll a = poss[xv];
    		//cout<<a<<'\n';
    		for (ll b = n-1; b>=a+1; b--){
    			if (mindist!=1e18&&c>=pathlength[b]-pathlength[a]){continue;}
    			//try express road linking a and b
    			ll mxdist = max(prefixrangemax[a],suffixrangemax[b]);
    			//try thing-on-left to thing-on-right
    			mxdist = max(mxdist,min(ll(c),pathlength[b]-pathlength[a])+suffixmax[b]+prefixmax[a]);
    			//try thing-on-left to middle, thing-on-right to middle
     
    			//segmenttree-ify
    			for (ll x = a; x<=b; x++){
    				if (x!=a){
    					mxdist = max(mxdist,
    						min(
    							pathlength[b]-pathlength[x]+c,
    							pathlength[x]-pathlength[a]
    							) + prefixmax[a] + d[x]);
    				}
    				if (x!=b){
    					mxdist = max(mxdist,
    						min(
    							pathlength[b]-pathlength[x],
    							pathlength[x]-pathlength[a]+c
    							) + suffixmax[b] + d[x]);
    				}
    				if (mxdist>mindist){break;}
    			}
    			if (mxdist>mindist){continue;}
    		
    			//try thing-on-middle to thing-on-middle
    			for (ll m = a; m<b; m++){
    				for (ll n = b; n>=a+1; n--){
    					//from m to n
    					mxdist = max(mxdist,
    						min(
    							c+pathlength[b]-pathlength[n]+pathlength[m]-pathlength[a],
    							pathlength[n]-pathlength[m]
    						)+d[n]+d[m]);
    					if (mxdist>mindist){break;}
    				}
    				if (mxdist>mindist){break;}
    			}
    			//cout<<a<<' '<<b<<": "<<mxdist<<'\n';
    			mindist = min(mindist, mxdist);
    		}
    	}
        return mindist;
    }

컴파일 시 표준 에러 (stderr) 메시지

shortcut.cpp: In function 'll find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:55:9: warning: variable 'endspluspath' set but not used [-Wunused-but-set-variable]
   55 |      ll endspluspath[1000000]={0};
      |         ^~~~~~~~~~~~
shortcut.cpp:56:9: warning: variable 'endsminuspath' set but not used [-Wunused-but-set-variable]
   56 |      ll endsminuspath[1000000]={0};
      |         ^~~~~~~~~~~~~

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