제출 #71536

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
71536		gnoor	Shortcut (IOI16_shortcut)	C++17	0 / 100	2 ms	432 KiB

shortcut

#include "shortcut.h"

#include <vector>
#include <algorithm>

using namespace std;

struct ei {
	long long dis;
	pair<int,int> range;
};

bool operator< (const ei &a, const ei &b) {
	return a.dis>b.dis;
}

pair<int,int> comb(const pair<int,int> &a, const pair<int,int> &b) {
	if (b.first>a.second) return {-1,-1};
	return {max(a.first,b.first),min(a.second,b.second)};
}

long long find_shortcut(int n, vector<int> l, vector<int> d, int c)
{
	vector<long long> qs(n,0);
	for (int i=1;i<n;i++) {
		qs[i]=l[i];
		qs[i]+=qs[i-1];
	}
	vector<ei> tbl;
	tbl.reserve(n*(n-1)/2);
	long long ans=0;
	long long mx=0;
	for (int i=0;i<n;i++) {
		for (int j=i+1;j<n;j++) {
			tbl.push_back(ei{qs[j]-qs[i]+d[j]+d[i],{i,j}});
			mx=max(mx,qs[j]-qs[i]+d[j]+d[i]);
		}
	}
	ans=mx;
	sort(tbl.begin(),tbl.end());
	pair<int,int> cur={0,n-1};
	long long curans;
	long long red;
	for (int i=0;i<(int)tbl.size();i++) {
		cur=comb(cur,tbl[i].range);
		if (cur.first==-1) break;
		red=qs[cur.second]-qs[cur.first]-c;
		if (red<=0) break;
		if (i==(int)tbl.size()-1||tbl[i+1].dis!=tbl[i].dis) {			
			curans=mx-red;
			if (i!=(int)tbl.size()-1) {
				curans=max(curans,tbl[i+1].dis);
			}
			ans=min(ans,curans);
		}
	}
	return ans;
}

• 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