Submission #128984

#	Time	Username	Problem	Language	Result	Execution time	Memory
128984		roseanne_pcy	Cake 3 (JOI19_cake3)	C++14	24 / 100	1448 ms	188132 KiB

cake3

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;

const int maxn = 2e3+5;

vector< ii > vec;

int n, k;

int v[maxn];
int w[maxn];

ll bst[maxn][maxn];

struct node
{
	int key, cnt, pr;
	ll tot;
	node *left, *right;
	node(int key) : key(key)
	{
		tot = key;
		cnt = 1;
		pr = (rand()<<16)^rand();
		left = right = NULL;
	}
	void calc()
	{
		tot = key;
		if(left) tot += left->tot;
		if(right) tot += right->tot;
		cnt = 1+(left?left->cnt:0)+(right?right->cnt:0);
	}
};

typedef node* ps;

ps merge(ps L, ps R)
{
	if(!L || !R) return L?L:R;
	if(L->pr> R->pr)
	{
		L->right = merge(L->right, R);
		L->calc();
		return L;
	}
	else
	{
		R->left = merge(L, R->left);
		R->calc();
		return R;
	}
}

pair<ps, ps> splitsz(ps big, int key)
{
	if(!big) return {big, big};
	int here = 1+(big->left?big->left->cnt:0);
	if(here<= key)
	{
		auto tmp = splitsz(big->right, key-here);
		big->right = tmp.X;
		big->calc();
		return {big, tmp.Y};
	}
	else
	{
		auto tmp = splitsz(big->left, key);
		big->left = tmp.Y;
		big->calc();
		return {tmp.X, big};
	}
}

pair<ps, ps> split(ps big, int key)
{
	if(!big) return {big, big};
	int here = big->key;
	if(here<= key)
	{
		auto tmp = split(big->right, key);
		big->right = tmp.X;
		big->calc();
		return {big, tmp.Y};
	}
	else
	{
		auto tmp = split(big->left, key);
		big->left = tmp.Y;
		big->calc();
		return {tmp.X, big};
	}
}

int main()
{
	scanf("%d %d", &n, &k);
	vec.resize(n);
	for(int i = 0; i< n; i++) scanf("%d %d", &vec[i].Y, &vec[i].X);
	sort(vec.begin(), vec.end());
	for(int i = 1; i<= n; i++)
	{
		v[i] = vec[i-1].Y;
		w[i] = vec[i-1].X;
	}
	for(int i = 1; i<= n; i++)
	{
		ps root = NULL;
		for(int j = i; j< (i+k-2)-1; j++)
		{
			auto tmp = split(root, v[j]);
			ps r1 = merge(tmp.X, new node(v[j]));
			root = merge(r1, tmp.Y);
		}
		for(int j = (i+k-2)-1; j<= n; j++)
		{
			auto tmp = split(root, v[j]);
			ps r1 = merge(tmp.X, new node(v[j]));
			root = merge(r1, tmp.Y);
			int tot = (j-i+1);
			tmp = splitsz(root, tot-(k-2));
			// printf("left %d\n", tot-(k-2));
			bst[i][j] = (tmp.Y)?(tmp.Y)->tot:0;
			// printf("bst[%d][%d] = %lld\n", i, j, bst[i][j]);
			root = merge(tmp.X, tmp.Y);
		}
	}
	ll best = -1e18;
	for(int i = 1; i<= n; i++)
	{
		for(int j = i+k-1; j<= n; j++)
		{
			best = max(best, bst[i+1][j-1]-2LL*(w[j]-w[i])+v[i]+v[j]);
		}
	}
	printf("%lld\n", best);
}

Compilation message (stderr)

cake3.cpp: In function 'int main()':
cake3.cpp:104:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &k);
  ~~~~~^~~~~~~~~~~~~~~~~
cake3.cpp:106:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0; i< n; i++) scanf("%d %d", &vec[i].Y, &vec[i].X);
                            ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 19 / 19
• Subtask 3: 0 / 76