oj.uz

Submission #114628

# Submission time Handle Problem Language Result Execution time Memory
114628 2019-06-02T05:47:13 Z davitmarg Shortcut (IOI16_shortcut) C++17
0 / 100
 2 ms 384 KB 
/*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)
{
	return pr[j] - (i ? pr[i - 1] : 0);
}

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]);
			}

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

			for (int i = r + 1; i < n; i++)
			{
				if (i == r + 1)
					mx += min(get(l,r),c)+p[i - 1];
				else
					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 + 1 < n)
				for (int i = r+1; i < n; i++)
					ans = mx + max(get(r + 1, i), get(l, r) + c - get(r + 1, i)) + d[i];

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

			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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB n = 4, incorrect answer: jury 80 vs contestant 90
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB n = 4, incorrect answer: jury 80 vs contestant 90
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB n = 4, incorrect answer: jury 80 vs contestant 90
2 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB n = 4, incorrect answer: jury 80 vs contestant 90
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB n = 4, incorrect answer: jury 80 vs contestant 90
2 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB n = 4, incorrect answer: jury 80 vs contestant 90
2 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB n = 4, incorrect answer: jury 80 vs contestant 90
2 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB n = 4, incorrect answer: jury 80 vs contestant 90
2 Halted 0 ms 0 KB -