Submission #600609

#	Time	Username	Problem	Language	Result	Execution time	Memory
600609		8e7	Shortcut (IOI16_shortcut)	C++17	23 / 100	2086 ms	2260 KiB

shortcut

#include "shortcut.h"
//Challenge: Accepted
#include <bits/stdc++.h>
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<vector<ll> > d(2*n, vector<ll>(2*n, 0));		
	vector<ll> pref(n, 0);
	for (int i = 0;i < n - 1;i++) pref[i+1] = pref[i] + L[i];
	
	for (int i = 0;i < 2*n;i++) {
		for (int j = i+1;j < 2*n;j++) {
			ll p = pref[j/2] - pref[i/2];	
			if (j % 2) p += D[j/2];
			if (i % 2) p += D[i/2];
			d[i][j] = d[j][i] = p;
		}
	}
	ll ans = inf;
	for (int a = 0;a < 2*n;a += 2) {
		for (int b = 2;b < 2*n;b += 2) {
			ll val = 0;
			for (int i = 0;i < 2*n;i++) {
				for (int j = i+1;j < 2*n;j++) {
					val = max(val, min(d[a][i] + d[b][j] + c, d[i][j]));	
				}
			}
			debug(a, b, val);
			ans = min(ans, val);
		}
	}
    return ans;
}

Compilation message (stderr)

shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
shortcut.cpp:44:4: note: in expansion of macro 'debug'
   44 |    debug(a, b, val);
      |    ^~~~~

• 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