oj.uz

답안 #114748

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
114748 2019-06-02T13:48:21 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 t[4 * 300005],D[4 * 300005];


void build(int v,int l,int r)
{
	t[v] = D[v] = 0;
	if (l == r)
		return;
	int m = (l + r) / 2;
	build(v * 2, l, m);
	build(v * 2 + 1, m + 1, r);
}

void push(int v, int l, int r)
{
	if (D[v] == 0)
		return;
	if (l != r)
	{
		D[v * 2] += D[v];
		D[v * 2 + 1] += D[v];
	}
	t[v] += D[v];
	D[v] = 0;
}

void update(int v, int l, int r, int i, int j,LL val)
{
	if (i > j)
		return;
	int m = (l + r) / 2;
	push(v, l, r);
	push(v * 2, l, m);
	push(v * 2 + 1, m + 1, r);
	if (l == i && r == j)
	{
		D[v] += val;
		push(v, l, r);
		return;
	}
	update(v * 2, l, m, i, min(j, m), val);
	update(v * 2 + 1, m + 1, r, max(i, m + 1), j, val);
	t[v] = max(t[v * 2], t[v * 2 + 1]);
}


LL get(int v, int l, int r, int i, int j)
{
	if (i > j)
		return 0;
	int m = (l + r) / 2;
	push(v, l, r);
	push(v * 2, l, m);
	push(v * 2 + 1, m + 1, r);
	if (l == i && r == j)
		return t[v];
	return max(
		get(v * 2, l, m, i, min(j, m)),
		get(v * 2 + 1, m + 1, r, max(i, m + 1), j)
	);
}

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

LL getMaxDist(vector<LL> p,vector<LL> d,LL all=0)
{
	p.PB(0);
	LL sum=0,ans=0;
	build(1,0,d.size()-1);
	int l, r;
	l = 0;
	r = 1;
	sum = p[r-1];
	update(1,0,d.size()-1,0,0,d[0]);
	while (r < d.size())
	{
		while (l<r && sum>all-sum)
		{
			LL val = get(1, 0, d.size() - 1, l, l);
			update(1, 0, d.size() - 1, l, l, -val);
			sum -= p[l];
			l++;
		}
		update(1, 0, d.size() - 1, l, r-1, p[r - 1]);
		if (l < r)
			ans = max(ans, get(1, 0, d.size() - 1, l, r - 1) + d[r]);
		update(1, 0, d.size() - 1, r, r, d[r]);
		sum += p[r];
		r++;
	}
	return ans;
}

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(getLen(l, i), getLen(l, r) + c - getLen(l, i)) + d[i]);

			mx += min(getLen(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(getLen(r, i), getLen(l, r) + c - getLen(r, i)) + d[i]);

			if (l != r)
			{
				vector<LL> P, D;
				for (int i = l; i <= r - 1; i++)
					P.PB(p[i]);
				for (int i = l; i <= r; i++)
					D.PB(d[i]);
				P.PB(c);
				for (int i = l; i <= r - 1; i++)
					P.PB(p[i]);
				for (int i = l; i <= r; i++)
					D.PB(d[i]);

				ans = max(ans, getMaxDist(P, D, getLen(l, r)));
			}
			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 


/*



*/

Compilation message

shortcut.cpp: In function 'long long int getMaxDist(std::vector<long long int>, std::vector<long long int>, long long int)':
shortcut.cpp:107:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (r < d.size())
         ~~^~~~~~~~~~

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB n = 4, 80 is a correct answer
2 Incorrect 2 ms 384 KB n = 9, incorrect answer: jury 110 vs contestant 100
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB n = 4, 80 is a correct answer
2 Incorrect 2 ms 384 KB n = 9, incorrect answer: jury 110 vs contestant 100
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB n = 4, 80 is a correct answer
2 Incorrect 2 ms 384 KB n = 9, incorrect answer: jury 110 vs contestant 100
3 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB n = 4, 80 is a correct answer
2 Incorrect 2 ms 384 KB n = 9, incorrect answer: jury 110 vs contestant 100
3 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB n = 4, 80 is a correct answer
2 Incorrect 2 ms 384 KB n = 9, incorrect answer: jury 110 vs contestant 100
3 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB n = 4, 80 is a correct answer
2 Incorrect 2 ms 384 KB n = 9, incorrect answer: jury 110 vs contestant 100
3 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB n = 4, 80 is a correct answer
2 Incorrect 2 ms 384 KB n = 9, incorrect answer: jury 110 vs contestant 100
3 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB n = 4, 80 is a correct answer
2 Incorrect 2 ms 384 KB n = 9, incorrect answer: jury 110 vs contestant 100
3 Halted 0 ms 0 KB -