#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()
{
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
colouring.cpp: In function 'int32_t main()':
colouring.cpp:60:7: warning: unused variable 'k' [-Wunused-variable]
60 | int k = i % 2;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
428 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
428 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
428 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
428 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
852 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
181 ms |
102400 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
428 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
