oj.uz

Submission #600731

# Submission time Handle Problem Language Result Execution time Memory
600731 2022-07-21T07:30:37 Z 8e7 Shortcut (IOI16_shortcut) C++17
0 / 100
 1 ms 300 KB 
#include "shortcut.h"
//Challenge: Accepted
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r){
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 100005
#define pii pair<int, int>
#define ff first
#define ss second
const ll inf = 1LL<<60;

int C;
ll ans = inf;
vector<int> D;
vector<ll> pref, suf, pma, sma, cy;
vector<ll> wei, p;	

ll getans(int a, int b){
	if (b <= a) return inf;
	ll val = max(pma[a], sma[b]);
	int siz = b - a + 1;
	ll tot = cy[b] - cy[a] + C;

	for (int i = a;i <= b;i++) {
		if (i == a) wei[i-a] = wei[i-a+siz] = pref[a];
		else if (i == b) wei[i-a] = wei[i-a+siz] = suf[b];
		else wei[i-a] = wei[i-a + siz] = D[i];		
	}
	for (int i = 0;i < siz;i++) {
		p[i] = cy[i+a] - cy[a];
		p[i+siz] = p[i] + tot;
	}
	deque<int> deq;
	for (int i = 0;i < 2 * siz;i++) {
		while (deq.size() && (p[i] - p[deq.front()])*2 > tot) deq.pop_front();
		if (deq.size()) val = max(val, wei[i] + wei[deq.front()] + p[i] - p[deq.front()]);
		while (deq.size() && wei[i] - p[i] >= wei[deq.back()] - p[deq.back()]) deq.pop_back();
		deq.push_back(i);
	}
	return val;
}
void solve(int l, int r, int ql, int qr) {
	if (r <= l || qr <= ql) return;
	int m = (l + r) / 2;
	ll bv = inf;	
	int bind = ql;
	for (int i = ql;i < qr;i++) {
		ll val = getans(m, i);
		if (val <= bv) {
			bv = val;
			bind = i;	
		}
	}
	debug(m, bind, bv);
	ans = min(ans, bv);
	solve(l, m, ql, bind+1), solve(m+1, r, bind, qr);
}
long long find_shortcut(int n, vector<int> L, vector<int> dd, int cost) {
	C = cost;
	D = dd;
	pref.resize(n);
	suf.resize(n);
	pma.resize(n);
	sma.resize(n);
	cy.resize(n);

	wei.resize(2*n), p.resize(2*n);
	for (int i = 0;i < n-1;i++) cy[i+1] = cy[i] + L[i];
	for (int i = 0;i < n;i++) {
		pref[i] = D[i];
		pma[i] = D[i];
		if (i) {
			pma[i] = max(pma[i] + pref[i-1] + L[i-1], pma[i-1]);
			pref[i] = max(pref[i], pref[i-1] + L[i-1]);
		}
	}
	for (int i = n - 1;i >= 0;i--) {
		suf[i] = D[i];
		sma[i] = D[i];
		if (i < n - 1) {
			sma[i] = max(sma[i] + suf[i+1] + L[i], sma[i+1]);
			suf[i] = max(suf[i], suf[i+1] + L[i]);
		}
	}
	solve(0, n, 0, n);
	return ans;
}

Compilation message

shortcut.cpp: In function 'void solve(int, int, int, int)':
shortcut.cpp:14:20: warning: statement has no effect [-Wunused-value]
   14 | #define debug(...) 0
      |                    ^
shortcut.cpp:66:2: note: in expansion of macro 'debug'
   66 |  debug(m, bind, bv);
      |  ^~~~~

Subtask #1
0 / 9.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 7.0

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

Subtask #5
0 / 33.0

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

Subtask #6
0 / 22.0

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

Subtask #7
0 / 4.0

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

Subtask #8
0 / 3.0

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