Submission #267143

#	Time	Username	Problem	Language	Result	Execution time	Memory
267143		mjkocijan	Shortcut (IOI16_shortcut)	C++14	23 / 100	2087 ms	384 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
#define MAXN 550
#define INF 1001001001001001001LL

ll pref[MAXN], ml[MAXN], mr[MAXN];

long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
	for (int i = 0; i < n - 1; i++) {
		pref[i] = (i ? pref[i - 1] : 0) + l[i];
	}
	ml[0] = d[0];
	for (int i = 0; i < n; i++) {
		
	}
	ll reza = INF;
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			//if (c > pref[j - 1] - (i ? pref[i - 1] : 0)) continue;
			
			ll rj = 0;
			
			for (int k = 0; k < n; k++) {
				for (int m = k + 1; m < n; m++) {
					ll r1 = d[k] + d[m] + pref[m - 1] - (k ? pref[k - 1] : 0);
					ll r2 = d[k] + d[m] + (k <= i ? (pref[i - 1] - (k ? pref[k - 1] : 0)) : (pref[k - 1] - (i ? pref[i - 1] : 0)))
															+ (m <= j ? (pref[j - 1] - (m ? pref[m - 1] : 0)) : (pref[m - 1] - (j ? pref[j - 1] : 0))) + c;
					
					rj = max(rj, min(r1, r2));
					//cout <<i<<'.'<<j<<' '<<k<<','<<m<<' '<<r1<<'.'<<r2<<endl;
				}
			}
			
			reza = min(reza, rj);
		}
	}
  return reza;
}

• Subtask 1: 9 / 9
• Subtask 2: 14 / 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