oj.uz

Submission #581207

# Submission time Handle Problem Language Result Execution time Memory
581207 2022-06-22T11:30:58 Z dozer Colouring a rectangle (eJOI19_colouring) C++14
0 / 100
 160 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(m);
	if (n < m) return 3;
	for (int i = 2; i <= max(n, m); i++)
	{
		int b = con[i - 1].front();
		int e = con[i - 1].back();
		int l = b - 1;
		if (l == 0) l += 2;
		int r = e + 1;
		if (r > n + m - 1) r -= 2;
		for (int j = l; j <= r; 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();
		int l = b + 1;
		int r = e - 1;
		for (int j = l; j <= r; 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) ? 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);
			//cout<<i<<sp<<j<<sp<<sp<<s<<sp<<t<<sp<<sp<<b<<sp<<e<<sp<<sp<<pre[t]<<sp<<pre[e]<<sp<<sp<<t1<<sp<<t2<<endl;
		}
	}
	
	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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Runtime error 1 ms 340 KB Execution failed because the return code was nonzero
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Runtime error 1 ms 340 KB Execution failed because the return code was nonzero
6 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 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Runtime error 1 ms 340 KB Execution failed because the return code was nonzero
6 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 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Runtime error 1 ms 340 KB Execution failed because the return code was nonzero
6 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 340 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 160 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 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Runtime error 1 ms 340 KB Execution failed because the return code was nonzero
6 Halted 0 ms 0 KB -