Submission #397334

#	Time	Username	Problem	Language	Result	Execution time	Memory
397334		peuch	Shortcut (IOI16_shortcut)	C++17	38 / 100	2079 ms	580 KiB

shortcut

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

vector<long long> val;
vector<long long> maxL, maxR;
vector<long long> maxDL, maxDR;
vector<long long> dist;
vector<long long> D;

int N;
long long cost;

struct maxQueue{
	deque<pair<long long, int> > d;
	long long soma;
	int ini, fim;
	maxQueue(){
		soma = 0;
		ini = 0, fim = -1;
	}
	void push(long long val){
		while(!d.empty() && d.back().first <= val - soma) d.pop_back();
		d.push_back(make_pair(val - soma, ++fim));
	}
	void pop(){
		if(!d.empty() && ini == d.front().second) d.pop_front();
		ini++;
	}
	long long getMax(){
		if(d.empty()) return 0;
		return d.front().first + soma;
	}
	void add(long long val){
		soma += val;
		
	}
};

long long getLen(int id, int ini, int fim){
	if(id > fim) id = ini;
	if(id == ini) return cost;
	return dist[id] - dist[id - 1];
}

long long test(int ini, int fim){
	val[ini] = maxL[ini];
	val[fim] = maxR[fim];
	long long diam = max(maxDL[ini], maxDR[fim]);
	if(ini != 0) diam = max(diam, maxL[ini - 1] + dist[ini] - dist[ini - 1] + D[ini]);
	if(fim != N - 1) diam = max(diam, maxR[fim + 1] + dist[fim + 1] - dist[fim] + D[fim]);
	long long sum = 0;
	long long tam = dist[fim] - dist[ini] + cost;
	int it = ini;
	
	
	maxQueue fila;
	fila.push(val[ini]);
	for(int i = ini + 1; i < fim; i++){
		fila.add(getLen(i, ini, fim));
		sum += getLen(i, ini, fim);
		val[i] = D[i];
		fila.push(val[i]);
	}
	fila.add(getLen(fim, ini, fim));
	sum += getLen(fim, ini, fim);
	while(2 * sum > tam){
		fila.pop();
		it++;
		if(it > fim) it = ini;
		sum -= getLen(it, ini, fim);
	}
	diam = max(diam, val[fim] + fila.getMax());
	fila.push(val[fim]);
	for(int i = ini; i < fim; i++){
		fila.add(getLen(i, ini, fim));
		sum += getLen(i, ini, fim);
		while(2 * sum > tam){
			fila.pop();
			it++;
			if(it > fim) it = ini;
			sum -= getLen(it, ini, fim);
		}
		diam = max(diam, val[i] + fila.getMax());
		fila.push(val[i]);
	}
	
	
	maxQueue fila2;
	it = fim;
	sum = 0;
	fila2.push(val[fim]);
	for(int i = fim - 1; i > ini; i--){
		fila2.add(getLen(i + 1, ini, fim));
		sum += getLen(i + 1, ini, fim);
		fila2.push(val[i]);
	}
	fila2.add(getLen(ini + 1, ini, fim));
	sum += getLen(ini + 1, ini, fim);
	while(2 * sum > tam){
		fila2.pop();
		sum -= getLen(it, ini, fim);
		it--;
		if(it < ini) it = fim;
	}	
	diam = max(diam, val[ini] + fila2.getMax());
	fila2.push(val[ini]);
	for(int i = fim; i > ini; i--){
		fila2.add(getLen(i + 1, ini, fim));
		sum += getLen(i + 1, ini, fim);
		while(2 * sum > tam){
			fila2.pop();
			sum -= getLen(it, ini, fim);
			it--;
			if(it < ini) it = fim;
		}	
		diam = max(diam, val[i] + fila2.getMax());
		fila2.push(val[i]);
	}
	
	
	return diam;
}

long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
	cost = c;
	N = n;
	dist = vector<long long> (n);
	val = vector<long long> (n);
	maxL = vector<long long> (n);
	maxR = vector<long long> (n); 
	maxDL = vector<long long> (n);
	maxDR = vector<long long> (n);
	D = vector<long long> (n);
	
	dist[0] = 0;
	long long len = 0;
	maxL[0] = d[0];
	D[0] = d[0];
	maxDL[0] = d[0];
	for(int i = 1; i < n; i++){
		dist[i] = dist[i - 1] + l[i - 1];
		maxDL[i] = max(maxDL[i - 1], d[i] + maxL[i - 1] + l[i - 1]);
		maxL[i] = max((long long)d[i], maxL[i - 1] + l[i - 1]);
		D[i] = d[i];
	}
	maxR[n - 1] = d[n - 1];
	maxDR[n - 1] = d[n - 1];
	for(int i = n - 2; i >= 0; i--){
		maxDR[i] = max(maxDR[i + 1], d[i] + maxR[i + 1] + l[i]);
		maxR[i] = max((long long)d[i], maxR[i + 1] + l[i]);
	}
	len = dist[n - 1];
	
	long long maxi = 0;
	int ini = 0;
	for(int i = 0; i < n; i++)
		if(d[i] + dist[i] > maxi) maxi = d[i] + dist[i], ini = i;
	maxi = 0;
	int fim = 0;
	for(int i = 0; i < ini; i++)
		if(dist[ini] - dist[i] + d[ini] + d[i] > maxi) maxi = dist[ini] - dist[i] + d[ini] + d[i], fim = i;
	for(int i = ini + 1; i < n; i++)
		if(dist[i] - dist[ini] + d[ini] + d[i] > maxi) maxi = dist[i] - dist[ini] + d[ini] + d[i], fim = i;
	
	if(ini > fim) swap(ini, fim);
	
	long long ans = maxi;
//	int j = ini + 1;
//	for(int i = ini; i < fim; i++){
//		j = max(j, i + 1);
//		while(1){
//			long long aux = test(i, j);
//			ans = min(ans, aux);
//			if(j == fim || aux > maxL[i] + maxR[j] + cost) break;
//			j++;
//		}
//	}
	
	for(int i = 0; i < n; i++)
		for(int j = i + 1; j < n; j++)
			ans = min(ans, test(i, j));
	
    return ans;
}

Compilation message (stderr)

shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:140:12: warning: variable 'len' set but not used [-Wunused-but-set-variable]
  140 |  long long len = 0;
      |            ^~~

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