Submission #581187

#	Time	Username	Problem	Language	Result	Execution time	Memory
581187		dozer	Colouring a rectangle (eJOI19_colouring)	C++14	0 / 100	169 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 4010
#define int long long

vector<int> con[N];
int dp[N][N], pre[N], cost[N];

int32_t main()
{
	fileio();
	fastio();

	int n, m;
	cin>>n>>m;
	con[1].pb(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++)
		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 = (i % 2 == 1 ? 1 : 2); 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; 
}

Compilation message (stderr)

colouring.cpp: In function 'int32_t main()':
colouring.cpp:61:7: warning: unused variable 'k' [-Wunused-variable]
   61 |   int k = i % 2;
      |       ^
colouring.cpp:9:25: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 | #define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
      |                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
colouring.cpp:19:2: note: in expansion of macro 'fileio'
   19 |  fileio();
      |  ^~~~~~
colouring.cpp:9:59: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 | #define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
      |                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
colouring.cpp:19:2: note: in expansion of macro 'fileio'
   19 |  fileio();
      |  ^~~~~~

• Subtask 1: 0 / 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