oj.uz

Submission #134784

# Submission time Handle Problem Language Result Execution time Memory
134784 2019-07-23T09:19:02 Z MAMBA Shortcut (IOI16_shortcut) C++17
0 / 100
 2 ms 376 KB 
#include "shortcut.h"
#include <bits/stdc++.h>

using namespace std;

#define rep(i , j , k) for(int i = j; i < (int)k; i++)

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;

inline bool smax(ll &a, ll b) {
	if (a < b) {
		a= b;
		return true;
	}
	return false;
}

inline bool smin(ll &a, ll b) {
	if (b < a) {
		a = b;
		return true;
	}
	return false;
}

ll find_shortcut(int n, vi D, vi I, int c)
{
	ll res = 1e18;

	vl pos(n);
	rep(i , 1 , n) pos[i] = pos[i - 1] + D[i - 1];

	vl gg(n), dd(n);

	{
		vi ts;
		rep(i , 0 , n) {
			gg[i] = i ? gg[i - 1]  : 0;
			if (ts.size())
				smax(gg[i] , pos[i] - pos[ts[0]] + I[i] + I[ts[0]]);
			while (ts.size() && pos[i] - pos[ts.back()] + I[ts.back()] <= I[i])
				ts.pop_back();


			ts.push_back(i);
		}
	}


	{
		vi ts;
		for (int i = n - 1; ~i; i--) {
			dd[i] = i + 1 < n ? dd[i + 1]  : 0;
			if (ts.size())
				smax(dd[i] , -(pos[i] - pos[ts[0]]) + I[i] + I[ts[0]]);
			while (ts.size() && -(pos[i] - pos[ts.back()]) + I[ts.back()] <= I[i])
				ts.pop_back();
			ts.push_back(i);
		}
	}



	auto f = [&](int l , int r) -> ll {

		vl junk(I.begin() + l , I.begin() + r + 1);
		rep(i , 0 , l) smax(junk[0] , I[i] + pos[l] - pos[i]);
		rep(i , r + 1, n) smax(junk.back() , I[i] + pos[i] - pos[r]);

		ll len = pos[r] - pos[l] + c;

		ll rr = max(gg[l] , dd[r]);


		deque<int> st;

		auto dist = [&](int l_ , int r_) -> ll {
			ll local = pos[r_] - pos[l_];
			if (l_ >= r_) local += len;
			return local;
		};

		auto push = [&](int p) {
			while (st.size()) {
				int u = st.back();
				if (u == p || dist(u , p) + junk[u - l] <= junk[p])
					st.pop_back();
				else break;
			}
			st.push_back(p);
		};

		auto relax = [&](int p) {

			while (st.size() > 1 && dist(st.front() , p) * 2 > len)
				st.pop_front();

		};

		rep(i , l , r + 1) {
			push(i);
			relax(i);
		}
		rep(i , l , r + 1) {
			push(i);
			int u = st.front();
			if (u != i) {
				ll shit = junk[u - l] + junk[i - l] + dist(u , i);
				smax(rr , shit);
			}
			relax(i);
		}
		return rr;
	};

	rep(i , 0 , n)
		rep(j , i + 1, n) {
				smin(res , f(i , j));
			//cout << i << ' '<< j << ' '<< endl;
			//cout << f(i , j ) << endl;
		}

	return res;

}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB n = 4, 80 is a correct answer
2 Correct 2 ms 376 KB n = 9, 110 is a correct answer
3 Correct 2 ms 376 KB n = 4, 21 is a correct answer
4 Correct 2 ms 256 KB n = 3, 4 is a correct answer
5 Incorrect 2 ms 256 KB n = 2, incorrect answer: jury 62 vs contestant 71
6 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB n = 4, 80 is a correct answer
2 Correct 2 ms 376 KB n = 9, 110 is a correct answer
3 Correct 2 ms 376 KB n = 4, 21 is a correct answer
4 Correct 2 ms 256 KB n = 3, 4 is a correct answer
5 Incorrect 2 ms 256 KB n = 2, incorrect answer: jury 62 vs contestant 71
6 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB n = 4, 80 is a correct answer
2 Correct 2 ms 376 KB n = 9, 110 is a correct answer
3 Correct 2 ms 376 KB n = 4, 21 is a correct answer
4 Correct 2 ms 256 KB n = 3, 4 is a correct answer
5 Incorrect 2 ms 256 KB n = 2, incorrect answer: jury 62 vs contestant 71
6 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB n = 4, 80 is a correct answer
2 Correct 2 ms 376 KB n = 9, 110 is a correct answer
3 Correct 2 ms 376 KB n = 4, 21 is a correct answer
4 Correct 2 ms 256 KB n = 3, 4 is a correct answer
5 Incorrect 2 ms 256 KB n = 2, incorrect answer: jury 62 vs contestant 71
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB n = 4, 80 is a correct answer
2 Correct 2 ms 376 KB n = 9, 110 is a correct answer
3 Correct 2 ms 376 KB n = 4, 21 is a correct answer
4 Correct 2 ms 256 KB n = 3, 4 is a correct answer
5 Incorrect 2 ms 256 KB n = 2, incorrect answer: jury 62 vs contestant 71
6 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB n = 4, 80 is a correct answer
2 Correct 2 ms 376 KB n = 9, 110 is a correct answer
3 Correct 2 ms 376 KB n = 4, 21 is a correct answer
4 Correct 2 ms 256 KB n = 3, 4 is a correct answer
5 Incorrect 2 ms 256 KB n = 2, incorrect answer: jury 62 vs contestant 71
6 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB n = 4, 80 is a correct answer
2 Correct 2 ms 376 KB n = 9, 110 is a correct answer
3 Correct 2 ms 376 KB n = 4, 21 is a correct answer
4 Correct 2 ms 256 KB n = 3, 4 is a correct answer
5 Incorrect 2 ms 256 KB n = 2, incorrect answer: jury 62 vs contestant 71
6 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB n = 4, 80 is a correct answer
2 Correct 2 ms 376 KB n = 9, 110 is a correct answer
3 Correct 2 ms 376 KB n = 4, 21 is a correct answer
4 Correct 2 ms 256 KB n = 3, 4 is a correct answer
5 Incorrect 2 ms 256 KB n = 2, incorrect answer: jury 62 vs contestant 71
6 Halted 0 ms 0 KB -