oj.uz

Submission #57836

# Submission time Handle Problem Language Result Execution time Memory
57836 2018-07-16T09:52:19 Z robert Shortcut (IOI16_shortcut) C++14
0 / 100
 3 ms 376 KB 
#include <iostream>
#include <vector>

using namespace std;

vector <long long> dist[2], maxd[2]; //1 asking from the right, i.e. int the left direction, 0 asking from the left
int N;
vector<int> l, d;
int c;

int dst(int a, int b){
	return dist[1][b]-dist[1][a];
}

long long find_shortcut(int n, vector<int> l_c, vector<int> d_c, int c_c){
	N = n;
	l = l_c;
	d = d_c;
	c = c_c;
	dist[0].assign(N+1, 0);
	maxd[0] = maxd[1] = dist[0];
	dist[1] = dist[0];
	dist[0][0] = dist[1][N-1] = 0;
	maxd[0][0] = d[0];
	maxd[1][N-1] = d[N-1];
	for(int x=1; x<N; x++){
		dist[0][x] = dist[0][x-1]+l[x-1];
		maxd[0][x] = max(maxd[0][x-1]+l[x-1], (long long)d[x]);
	}
	for(int x = N-2; x>=0; x--){
		dist[1][x] = dist[1][x+1]+l[x];
		maxd[1][x] = max(maxd[1][x+1]+l[x], (long long)d[x]);
	}
	long long a = 0;
	for(int x=0; x<N; x++){
		a = max(a, maxd[0][x]+maxd[1][x]);
		cout << dist[0][x] << " " << dist[1][x] << endl;
		cout << maxd[0][x] << " " << maxd[1][x] << endl;
	}
	for(int x=0; x<N-1; x++){
		for(int y=x+1; y<N; y++){
			//count the maxdist if we put a node between x and y
			long long nmxd = c+maxd[1][y]+maxd[0][x];
			if(nmxd<a)
				cout << x << " " << y << endl;
			for(int z=x+1; z<y; z++){
				nmxd = max(nmxd, (long long)min(dst(z, y), dst(x, z)+c));
				nmxd = max(nmxd, (long long)min(dst(z, y)+c, dst(x, z)));
				for(int z1 = z+1; z1<y; z1++){
					nmxd = max(nmxd, (long long)d[z]+d[z1]+min(dst(z, z1), dst(x, z)+c+dst(z1, y)));
				}
			}
			if(nmxd<a)
				cout << x << " " << y << " " << nmxd << endl;
			a = min(a, nmxd);
		}
	}
	return a;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Secret is incorrect!
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Secret is incorrect!
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Secret is incorrect!
2 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Secret is incorrect!
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Secret is incorrect!
2 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Secret is incorrect!
2 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Secret is incorrect!
2 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Secret is incorrect!
2 Halted 0 ms 0 KB -