Submission #114650

#	Time	Username	Problem	Language	Result	Execution time	Memory
114650		davitmarg	Shortcut (IOI16_shortcut)	C++17	31 / 100	2035 ms	504 KiB

shortcut

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <ctype.h>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin (),v.end()
using namespace std;
int n;
vector<LL> p, d, pr;
LL c,best=mod*mod;

LL get(int i,int j)
{
	if (i > j)
		swap(i, j);
	return pr[j] - pr[i];
}

int Main()
{
	pr.resize(n);
	for (int i = 1; i < n; i++)
		pr[i] = pr[i - 1] + p[i - 1];
	for (int l = 0; l < n; l++)
		for (int r = l+1; r < n; r++)
		{
			LL ans = -mod * mod;
			LL mx = d[0];
			ans = mx;
			for (int i = 1; i < l; i++)
			{
				mx += p[i - 1];
				ans = max(ans, mx + d[i]);
				mx = max(mx, d[i]);
			}
			ans = max(ans,mx);
			if (l - 1 >= 0)
				mx += p[l - 1];
			if (l - 1 >= 0)
				for (int i = l; i <= r; i++)
					ans = max(ans,mx + min(get(l, i), get(l, r) + c - get(l, i)) + d[i]);

			mx += min(get(l, r), c);
			for (int i = r + 1; i < n; i++)
			{
				mx += p[i - 1];
			
				ans = max(ans, mx + d[i]);
				mx = max(mx, d[i]);
			}

			mx = d[n-1];
			for (int i = n - 2; i > r; i--)
			{
				mx += p[i];
				ans = max(ans, mx + d[i]);
				mx = max(mx, d[i]);
			}
			if (r < n-1)
				mx += p[r];

			ans = max(ans, mx);
			if (r + 1 < n)
				for (int i = l; i <= r; i++)
					ans = max(ans, mx + min(get(r, i), get(l, r) + c - get(r, i)) + d[i]);

			for (int i = l; i <= r; i++)
				for (int j = i+1; j <= r; j++)
					ans = max(ans, d[i] + d[j] + min(get(i, j), get(l, r) + c - get(i, j)));
			
			for (int i = 0; i < n; i++)
				ans = max(ans,d[i]);

			best = min(best,ans);
		}

	return 0;
}

LL find_shortcut(int N,vector<int> L, vector<int> D,int C)
{
	n = N;
	for (int i = 0; i < n - 1; i++)
		p.PB(L[i]);
	for (int i = 0; i < n; i++)
		d.PB(D[i]);
	c = C;
	Main();
	return best;
}

#ifdef death

int main()
{
	int N,C;
	vector<int> L, D;
	cin >> N >> C;
	for (int i = 0; i < N-1; i++)
	{
		L.PB(0);
		cin >> L.back();
	}
	for (int i = 0; i < N; i++)
	{
		D.PB(0);
		cin >> D.back();
	}
	cout << find_shortcut(N,L,D,C) << endl;
	return 0;
}

#endif 


/*



*/

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