제출 #1258248

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1258248		kl0989e	도시들 (IOI15_towns)	C++20	13 / 100	134 ms	1240 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pi pair<int, int>
#define pl pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()

const int maxn=110;

vector<vi> dist(4*maxn,vi(4*maxn));

int hubDistance(int n, int sub) {
	for (int i=0; i<n; i++) {
		dist[i][i]=0;
		for (int j=i+1; j<n; j++) {
			dist[i][j]=getDistance(i,j);
			dist[j][i]=dist[i][j];
		}
	}
	int ans=2e9;
	for (int i=0; i<n; i++) {
		for (int j=i+1; j<n; j++) {
			map<int,int> dst;
			for (int k=0; k<n; k++) {
				if (k==i || k==j) {
					continue;
				}
				dst[(dist[i][k]+dist[i][j]-dist[j][k])/2]=max(dst[(dist[i][k]+dist[i][j]-dist[j][k])/2],(dist[i][k]+dist[j][k]-dist[i][j])/2);
			}
			int val=0;
			int prv=0;
			map<int,int> nw;
			for (auto pt=dst.begin(); pt!=dst.end(); pt++) {
				val+=pt->fi-prv;
				prv=pt->fi;
				nw[pt->fi]=max(pt->se,val);
				val=nw[pt->fi];
			}
			prv=dist[i][j];
			val=0;
			auto pt=dst.end();
			do {
				pt--;
				val+=prv-pt->fi;
				prv=pt->fi;
				val=max(val,pt->se);
				pt->se=max(val,nw[pt->fi]);
				ans=min(ans,pt->se);
			} while (pt!=dst.begin());
		}
	}
	return ans;
}

• Subtask 1: 13 / 13
• Subtask 2: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39