oj.uz

Submission #577856

# Submission time Handle Problem Language Result Execution time Memory
577856 2022-06-15T10:15:33 Z dozer Colouring a rectangle (eJOI19_colouring) C++14
20 / 100
 134 ms 44344 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 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.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 22228 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 36240 KB Output is correct
2 Correct 134 ms 36376 KB Output is correct
3 Correct 130 ms 44068 KB Output is correct
4 Correct 127 ms 44344 KB Output is correct
5 Correct 126 ms 44332 KB Output is correct
6 Correct 117 ms 41392 KB Output is correct
7 Correct 121 ms 43724 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -