oj.uz

Submission #577778

# Submission time Handle Problem Language Result Execution time Memory
577778 2022-06-15T09:01:32 Z dozer Colouring a rectangle (eJOI19_colouring) C++14
10 / 100
 152 ms 102400 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Incorrect 1 ms 468 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Incorrect 1 ms 468 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Incorrect 1 ms 468 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 852 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 152 ms 102400 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Incorrect 1 ms 468 KB Output isn't correct
14 Halted 0 ms 0 KB -