Submission #577778

#	Time	Username	Problem	Language	Result	Execution time	Memory
577778		dozer	Colouring a rectangle (eJOI19_colouring)	C++14	10 / 100	152 ms	102400 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 4005
#define int long long
vector<int> con[N];
int dp[N][N], pre[N], cost[N];

int32_t main()
{
	fastio();


	int n, m;
	cin>>n>>m;
	con[1].pb(min(n, m));
	for (int i = 2; i <= min(n, m); i++)
	{
		int b = con[i - 1].front();
		int e = con[i - 1].back();
		for (int j = b - 1; j <= e + 1; j += 2)
			con[i].pb(j);
	}
	for (int i = min(n, m) + 1; i <= max(n, m); i++)
	{
		int b = con[i - 1].front();
		int e = con[i - 1].back();
		for (int j = b + 1; j <= e + 1; j += 2)
			con[i].pb(j);
	}
	for (int i = max(n, m) + 1; i <= n + m - 1; i++)
	{
		int b = con[i - 1].front();
		int e = con[i - 1].back();
		for (int j = b + 1; j <= e - 1; j += 2)
			con[i].pb(j);
	}
/*
	for (int i = 1; i <= n + m - 1; i++)
	{
		cout<<i<<sp<<": ";
		for (auto j : con[i]) cout<<j<<sp;
		cout<<endl;
	}
*/
	for (int i = 1; i <= n + m - 1; i++)
		cin>>cost[i];
	int tmp;
	cin>>tmp;
	pre[1] = tmp;
	for (int i = 2; i <= n + m - 1; i++)
	{
		int num;
		cin>>num;
		pre[i] = pre[i - 2] + num;
	}

	for (int i = m + n - 1; i >= 1; i--)
	{
		int k = i % 2;
		dp[i][0] = min(cost[i] + dp[i + 2][0], pre[con[i].back()] - pre[max(con[i].front() - 2, (long long)0)] + dp[i + 2][i]);
		for (int j = (k + 1) % 2 + 1; j < i; j += 2)
		{
			int t1 = dp[i + 2][j] + cost[i];
			int t2 = dp[i + 2][i];
			int b = con[j].front(), e = con[j].back();
			int s = con[i].front(), t = con[i].back();
			if (s < b) t2 += pre[max(b - 2, (long long)0)] - pre[max(s - 2, (long long)0)];
			if (e < t) t2 += pre[t] - pre[e];
			dp[i][j] = min(t1, t2);
		}
	}
	
	int ans = dp[1][0];
	if (n + m - 1 >= 2) ans += dp[2][0];
	cout<<ans<<endl;
	
	cerr<<"time taken: "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
	return 0; 
}

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