Submission #600689

#	Time	Username	Problem	Language	Result	Execution time	Memory
600689		8e7	Shortcut (IOI16_shortcut)	C++17	0 / 100	1 ms	212 KiB

shortcut

#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;
long long find_shortcut(int n, vector<int> L, vector<int> D, int C) {
	vector<ll> pref(n, 0), suf(n, 0), pma(n, 0), sma(n, 0), cy(n, 0);
	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]);
		}
	}
	vector<ll> wei(2*n, 0), p(2*n, 0);	
	ll ans = inf;
	for (int a = 0;a < n;a ++) {
		for (int b = a+1;b < n;b++) {
			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);
			}
			debug(a, b, val);
			*/
			for (int i = 0;i < 2*siz;i++) {
				for (int j = i-1;j >= 0;j--) {
					if ((p[i] - p[j]) * 2 >= tot) val = max(val, p[i] - p[j] + wei[i] + wei[j]);
				}
			}
			ans = min(ans, val);
		}
	}
    return ans;
}

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