Submission #932345

#	Time	Username	Problem	Language	Result	Execution time	Memory
932345		siewjh	Shortcut (IOI16_shortcut)	C++17	38 / 100	387 ms	4440 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 505;
const ll inf = 1e18;
ll pref[MAXN], mxdl[MAXN][MAXN], mxdr[MAXN][MAXN], pans[MAXN], sans[MAXN];

ll find_shortcut(int nums, vector<int> len, vector<int> br, int exp){
    pref[0] = 0;
    for (int i = 1; i < nums; i++) pref[i] = pref[i - 1] + len[i - 1];
    for (int l = 0; l < nums; l++){
		mxdl[l][l] = br[l];
		for (int i = l + 1; i < nums; i++) mxdl[i][l] = max(mxdl[i - 1][l] + len[i - 1], (ll)(br[i]));
	}
	for (int r = nums - 1; r >= 0; r--){
		mxdr[r][r] = br[r];
		for (int i = r - 1; i >= 0; i--) mxdr[i][r] = max(mxdr[i + 1][r] + len[i], (ll)(br[i]));
	}
	pans[0] = br[0];
	for (int i = 1; i < nums; i++) pans[i] = max(pans[i - 1], mxdl[i - 1][0] + len[i - 1] + br[i]);
	sans[nums - 1] = br[nums - 1];
	for (int i = nums - 2; i >= 0; i--) sans[i] = max(sans[i + 1], mxdr[i + 1][nums - 1] + len[i] + br[i]);
    ll ans = inf;
    for (int l = 0; l < nums; l++)
		for (int r = l + 1; r < nums; r++){
			ll expd = min((ll)(exp), pref[r] - pref[l]), res = mxdl[l][0] + expd + mxdr[r][nums - 1];
			res = max(res, pans[l]);
			res = max(res, sans[r]);
			for (int i = l + 1; i < r; i++){
				res = max(res, mxdl[l][0] + min(pref[i] - pref[l], pref[r] - pref[i] + expd) + br[i]);
				res = max(res, min(pref[r] - pref[i], pref[i] - pref[l] + expd) + mxdr[r][nums - 1] + br[i]);
			}
			for (int i = l + 1; i < r; i++){
				int lo = i, hi = r - 1, far;
				while (lo <= hi){
					int m = (lo + hi) >> 1;
					if (pref[m] - pref[i] <= pref[i] - pref[l] + expd + pref[r] - pref[m]){
						far = m;
						lo = m + 1;
					}
					else hi = m - 1;
				}
				if (far != i) res = max(res, br[i] + mxdr[i + 1][far] + len[i]);
				if (far != r - 1) res = max(res, br[i] + pref[i] - pref[l] + mxdl[r - 1][far + 1] + len[r - 1] + expd);
			}
			ans = min(ans, res);
		}
	return ans;
}

Compilation message (stderr)

shortcut.cpp: In function 'll find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:45:82: warning: 'far' may be used uninitialized in this function [-Wmaybe-uninitialized]
   45 |     if (far != r - 1) res = max(res, br[i] + pref[i] - pref[l] + mxdl[r - 1][far + 1] + len[r - 1] + expd);
      |                                                                              ~~~~^~~

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