Submission #20624

#	Time	Username	Problem	Language	Result	Execution time	Memory
20624		model_code	Shortcut (IOI16_shortcut)	C++11	23 / 100	2000 ms	17644 KiB

shortcut

// name = sol_nk_n4.cpp, type = cpp.g++11

#include "shortcut.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using D = double;
using uint = unsigned int;

#ifdef WIN32
    #define LLD "%I64d"
#else
    #define LLD "%lld"
#endif

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

const int maxn = 1000005;
const ll inf = 1e18;

ll x[maxn], d[maxn];
int n, m, C;

ll calc(int a, int b)
{
	ll curd = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = i + 1; j < n; j++)
		{
			curd = max(curd, min(d[i] + d[j] + x[j] - x[i], d[i] + d[j] + abs(x[i] - x[a]) + abs(x[j] - x[b]) + C));
		}
	}
	return curd;
}

long long find_shortcut(int N, vector <int> L0, vector <int> L, int C_)
{
	n = N;
	C = C_;
	ll cursum = 0;
	for (int i = 0; i < n; i++)
	{
		d[i] = L[i];
		x[i] = cursum;
		if (i + 1 < n) cursum += L0[i];
	}
	long long result = inf;
	int end1 = 0;
	int end2 = 1;
	for (int i = 0; i < n; i++)
	{
		for (int j = i + 1; j < n; j++)
		{
			ll curans = calc(i, j);
			if (curans < result)
			{
				result = curans;
				end1 = i;
				end2 = j;
			}
		}
	}
	
	return result;
}

Compilation message (stderr)

shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:56:6: warning: variable 'end1' set but not used [-Wunused-but-set-variable]
  int end1 = 0;
      ^
shortcut.cpp:57:6: warning: variable 'end2' set but not used [-Wunused-but-set-variable]
  int end2 = 1;
      ^

• 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