oj.uz

Submission #397320

# Submission time Handle Problem Language Result Execution time Memory
397320 2021-05-01T22:22:56 Z peuch Shortcut (IOI16_shortcut) C++17
0 / 100
 1 ms 204 KB 

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

vector<long long> val;
vector<long long> maxL, maxR;
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 = 0;
	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); 
	D = vector<long long> (n);
	
	dist[0] = 0;
	long long len = 0;
	maxL[0] = d[0];
	D[0] = d[0];
	for(int i = 1; i < n; i++){
		dist[i] = dist[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];
	for(int i = n - 2; i >= 0; 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++;
		}
	}
	
    return ans;
}

Compilation message

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

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB n = 4, 80 is a correct answer
2 Correct 1 ms 204 KB n = 9, 110 is a correct answer
3 Correct 1 ms 204 KB n = 4, 21 is a correct answer
4 Correct 1 ms 204 KB n = 3, 4 is a correct answer
5 Correct 1 ms 204 KB n = 2, 62 is a correct answer
6 Correct 1 ms 204 KB n = 2, 3 is a correct answer
7 Correct 1 ms 204 KB n = 3, 29 is a correct answer
8 Correct 1 ms 204 KB n = 2, 3 is a correct answer
9 Correct 1 ms 204 KB n = 2, 3 is a correct answer
10 Correct 1 ms 204 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 204 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 204 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 204 KB n = 3, 3000000000 is a correct answer
14 Incorrect 1 ms 204 KB n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000
15 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB n = 4, 80 is a correct answer
2 Correct 1 ms 204 KB n = 9, 110 is a correct answer
3 Correct 1 ms 204 KB n = 4, 21 is a correct answer
4 Correct 1 ms 204 KB n = 3, 4 is a correct answer
5 Correct 1 ms 204 KB n = 2, 62 is a correct answer
6 Correct 1 ms 204 KB n = 2, 3 is a correct answer
7 Correct 1 ms 204 KB n = 3, 29 is a correct answer
8 Correct 1 ms 204 KB n = 2, 3 is a correct answer
9 Correct 1 ms 204 KB n = 2, 3 is a correct answer
10 Correct 1 ms 204 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 204 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 204 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 204 KB n = 3, 3000000000 is a correct answer
14 Incorrect 1 ms 204 KB n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000
15 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB n = 4, 80 is a correct answer
2 Correct 1 ms 204 KB n = 9, 110 is a correct answer
3 Correct 1 ms 204 KB n = 4, 21 is a correct answer
4 Correct 1 ms 204 KB n = 3, 4 is a correct answer
5 Correct 1 ms 204 KB n = 2, 62 is a correct answer
6 Correct 1 ms 204 KB n = 2, 3 is a correct answer
7 Correct 1 ms 204 KB n = 3, 29 is a correct answer
8 Correct 1 ms 204 KB n = 2, 3 is a correct answer
9 Correct 1 ms 204 KB n = 2, 3 is a correct answer
10 Correct 1 ms 204 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 204 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 204 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 204 KB n = 3, 3000000000 is a correct answer
14 Incorrect 1 ms 204 KB n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000
15 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB n = 4, 80 is a correct answer
2 Correct 1 ms 204 KB n = 9, 110 is a correct answer
3 Correct 1 ms 204 KB n = 4, 21 is a correct answer
4 Correct 1 ms 204 KB n = 3, 4 is a correct answer
5 Correct 1 ms 204 KB n = 2, 62 is a correct answer
6 Correct 1 ms 204 KB n = 2, 3 is a correct answer
7 Correct 1 ms 204 KB n = 3, 29 is a correct answer
8 Correct 1 ms 204 KB n = 2, 3 is a correct answer
9 Correct 1 ms 204 KB n = 2, 3 is a correct answer
10 Correct 1 ms 204 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 204 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 204 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 204 KB n = 3, 3000000000 is a correct answer
14 Incorrect 1 ms 204 KB n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000
15 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB n = 4, 80 is a correct answer
2 Correct 1 ms 204 KB n = 9, 110 is a correct answer
3 Correct 1 ms 204 KB n = 4, 21 is a correct answer
4 Correct 1 ms 204 KB n = 3, 4 is a correct answer
5 Correct 1 ms 204 KB n = 2, 62 is a correct answer
6 Correct 1 ms 204 KB n = 2, 3 is a correct answer
7 Correct 1 ms 204 KB n = 3, 29 is a correct answer
8 Correct 1 ms 204 KB n = 2, 3 is a correct answer
9 Correct 1 ms 204 KB n = 2, 3 is a correct answer
10 Correct 1 ms 204 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 204 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 204 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 204 KB n = 3, 3000000000 is a correct answer
14 Incorrect 1 ms 204 KB n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000
15 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB n = 4, 80 is a correct answer
2 Correct 1 ms 204 KB n = 9, 110 is a correct answer
3 Correct 1 ms 204 KB n = 4, 21 is a correct answer
4 Correct 1 ms 204 KB n = 3, 4 is a correct answer
5 Correct 1 ms 204 KB n = 2, 62 is a correct answer
6 Correct 1 ms 204 KB n = 2, 3 is a correct answer
7 Correct 1 ms 204 KB n = 3, 29 is a correct answer
8 Correct 1 ms 204 KB n = 2, 3 is a correct answer
9 Correct 1 ms 204 KB n = 2, 3 is a correct answer
10 Correct 1 ms 204 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 204 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 204 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 204 KB n = 3, 3000000000 is a correct answer
14 Incorrect 1 ms 204 KB n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000
15 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB n = 4, 80 is a correct answer
2 Correct 1 ms 204 KB n = 9, 110 is a correct answer
3 Correct 1 ms 204 KB n = 4, 21 is a correct answer
4 Correct 1 ms 204 KB n = 3, 4 is a correct answer
5 Correct 1 ms 204 KB n = 2, 62 is a correct answer
6 Correct 1 ms 204 KB n = 2, 3 is a correct answer
7 Correct 1 ms 204 KB n = 3, 29 is a correct answer
8 Correct 1 ms 204 KB n = 2, 3 is a correct answer
9 Correct 1 ms 204 KB n = 2, 3 is a correct answer
10 Correct 1 ms 204 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 204 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 204 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 204 KB n = 3, 3000000000 is a correct answer
14 Incorrect 1 ms 204 KB n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000
15 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB n = 4, 80 is a correct answer
2 Correct 1 ms 204 KB n = 9, 110 is a correct answer
3 Correct 1 ms 204 KB n = 4, 21 is a correct answer
4 Correct 1 ms 204 KB n = 3, 4 is a correct answer
5 Correct 1 ms 204 KB n = 2, 62 is a correct answer
6 Correct 1 ms 204 KB n = 2, 3 is a correct answer
7 Correct 1 ms 204 KB n = 3, 29 is a correct answer
8 Correct 1 ms 204 KB n = 2, 3 is a correct answer
9 Correct 1 ms 204 KB n = 2, 3 is a correct answer
10 Correct 1 ms 204 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 204 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 204 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 204 KB n = 3, 3000000000 is a correct answer
14 Incorrect 1 ms 204 KB n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000
15 Halted 0 ms 0 KB -