oj.uz

Submission #577820

# Submission time Handle Problem Language Result Execution time Memory
577820 2022-06-15T09:36:59 Z dozer Colouring a rectangle (eJOI19_colouring) C++14
0 / 100
 52 ms 19436 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 100005
#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 - 1];
		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 - 1] + val[e + 1] - val[b];
	}
	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 - 1] - val[b] - val[e];
	}


	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--)
	{
		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 1 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 52 ms 19436 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 29 ms 8336 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

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