Submission #577856

#	Time	Username	Problem	Language	Result	Execution time	Memory
577856		dozer	Colouring a rectangle (eJOI19_colouring)	C++14	20 / 100	134 ms	44344 KiB

colouring

#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n"
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define N 400005
#define int long long

int tot[N], cost[N], pre[N], sum[N], val[N];
vector<int> con[N];

const int modulo = 2e18 + 7;
int32_t main()
{
	fastio();

	int n, m;
	cin>>n>>m;
	cin>>cost[1];
	for (int i = 2; i <= n + m - 1; i++)
		cin>>cost[i];
	for (int i = 1; i < n; i++)
		cost[i] += cost[2 * n - i];
	sum[1] = cost[1];
	for (int i = 2; i <= n; i++)
		sum[i] = sum[i - 2] + cost[i];


	cin>>val[1];
	pre[1] = val[1];
	for (int i = 2; i <= n + m - 1; i++)
	{
		cin>>val[i];
		pre[i] = pre[i - 2] + val[i];
	}
	con[1].pb(min(n, m));
	tot[1] = val[con[1].front()];
	for (int i = 2; i <= min(n, m); i++)
	{
		int b = con[i - 1].front();
		int e = con[i - 1].back();
		con[i].pb(b - 1);
		con[i].pb(e + 1);
		tot[i] = tot[i - 2];
		tot[i] += val[b - 1];
		tot[i] += val[e + 1];
	}
	for (int i = min(n, m) + 1; i <= max(n, m); i++)
	{
		int b = con[i - 1].front();
		int e = con[i - 1].back();
		con[i].pb(b + 1);
		con[i].pb(e + 1);
		tot[i] = tot[i - 2];
		if (con[i - 1].front() <= b - 1) tot[i] -= val[b - 1];
		if (con[i - 1].back() < e + 1) tot[i] += val[e + 1]; 
	}
	for (int i = max(n, m) + 1; i <= n + m - 1; i++)
	{
		int b = con[i - 1].front();
		int e = con[i - 1].back();
		con[i].pb(b + 1);
		if (b + 1 != e - 1) con[i].pb(e - 1);
		tot[i] = tot[i - 2];
		if (con[i - 2].front() <= b - 1) tot[i] -= val[b - 1];
		if (con[i - 2].back() >= e + 1) tot[i] -= val[e + 1];
	}

	int ans = modulo;
	for (int i = max(n, m); i >= 0; i-= 2)
	{
		int tmp = sum[n] - sum[i] + tot[i];
		ans = min(ans, tmp);
	}
	int res = ans;
	ans = modulo;
	for (int i = max(n, m) - 1; i >= 0; i-=2)
	{
		int tmp = sum[n - 1] - sum[i] + tot[i];
		ans = min(ans, tmp);
	}

	res += ans;
	cout<<res<<endl;
	cerr<<"time taken: "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
	return 0; 
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 10
• Subtask 6: 20 / 20
• Subtask 7: 0 / 20