#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ld long double
#define ll long long
#define int long long
mt19937 rnd(51);
int n, m;
bool connect(int i, int j, int ii, int jj){
set<pair<int,int>> st;
while(i < n && j < m){
st.insert({i, j});
i++, j++;
}
while(ii < n && jj >= 0){
if (st.find({ii, jj}) != st.end()) return 1;
ii++, jj--;
}
return 0;
}
int take_ans(vector<pair<pair<int,int>, int>> a, vector<pair<pair<int,int>, int>> b){
if (a.size() == 0 || b.size() == 0){
return 0;
}
vector<pair<int,int>> need(b.size());
vector<vector<vector<int>>> dp(b.size() + 1, vector<vector<int>>(a.size() + 1, vector<int>(a.size() + 1, 1e18)));
int l = -1, r = -1;
for (int i = 0; i < a.size(); i++){
if (connect(a[i].first.first, a[i].first.second, b[0].first.first, b[0].first.second)){
l = i, r = i;
break;
}
}
for (int j = 0; j < b.size(); j++){
while(l - 1 >= 0 && connect(a[l - 1].first.first, a[l - 1].first.second, b[j].first.first, b[j].first.second)){
l--;
}
while(!connect(a[l].first.first, a[l].first.second, b[j].first.first, b[j].first.second)){
l++;
}
while(!connect(a[r].first.first, a[r].first.second, b[j].first.first, b[j].first.second)){
r--;
}
while(r + 1 < a.size() && connect(a[r + 1].first.first, a[r + 1].first.second, b[j].first.first, b[j].first.second)){
r++;
}
if (l <= r){
need[j] = {l, r};
}
}
dp[0][a.size()][a.size()] = 0;
for (int i = 1; i <= b.size(); i++){
for (int j = 0; j <= a.size(); j++){
for (int k = 0; k <= a.size(); k++){
dp[i][j][k] = min(dp[i][j][k], b[i - 1].second + dp[i - 1][j][k]);
int add = dp[i - 1][j][k];
if (j == a.size() && k == a.size()){
for (int f = need[i - 1].first; f <= need[i - 1].second; f++) add += a[f].second;
dp[i][need[i - 1].first][need[i - 1].second] = min(dp[i][need[i - 1].first][need[i - 1].second], add);
}
else{
if (need[i - 1].second < j || need[i - 1].first > k){
for (int f = need[i - 1].first; f <= need[i - 1].second; f++) add += a[f].second;
dp[i][need[i - 1].first][need[i - 1].second] = min(dp[i][need[i - 1].first][need[i - 1].second], add);
}
else{
for (int f = k + 1; f <= need[i - 1].second; f++) add += a[f].second;
for (int f = need[i - 1].first; f < j; f++) add += a[f].second;
dp[i][need[i - 1].first][need[i - 1].second] = min(dp[i][need[i - 1].first][need[i - 1].second], add);
}
}
}
}
}
int ans = 1e18;
for (int i = 0; i <= a.size(); i++) for (int j = 0; j <= a.size(); j++) ans = min(ans, dp[b.size()][i][j]);
return ans;
}
signed main()
{
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
vector<pair<pair<int,int>, int>> l0, l1, r0, r1;
int f = 0, s = m - 1;
for (int i = 0; i < n + m - 1; i++){
int a;
cin >> a;
if ((f + s) & 1){
l1.pb({{f, s}, a});
}
else{
l0.pb({{f, s}, a});
}
if (s > 0) s--;
else f++;
}
f = 0, s = 0;
for (int i = 0; i < n + m - 1; i++){
int a;
cin >> a;
if ((f + s) & 1){
r1.pb({{f, s}, a});
}
else{
r0.pb({{f, s}, a});
}
if (s + 1 < m) s++;
else f++;
}
cout << take_ans(l0, r0) + take_ans(l1, r1) << endl;
return 0;
}
Compilation message
colouring.cpp: In function 'long long int take_ans(std::vector<std::pair<std::pair<long long int, long long int>, long long int> >, std::vector<std::pair<std::pair<long long int, long long int>, long long int> >)':
colouring.cpp:34:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for (int i = 0; i < a.size(); i++){
| ~~^~~~~~~~~~
colouring.cpp:40:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for (int j = 0; j < b.size(); j++){
| ~~^~~~~~~~~~
colouring.cpp:50:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | while(r + 1 < a.size() && connect(a[r + 1].first.first, a[r + 1].first.second, b[j].first.first, b[j].first.second)){
| ~~~~~~^~~~~~~~~~
colouring.cpp:58:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for (int i = 1; i <= b.size(); i++){
| ~~^~~~~~~~~~~
colouring.cpp:59:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for (int j = 0; j <= a.size(); j++){
| ~~^~~~~~~~~~~
colouring.cpp:60:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for (int k = 0; k <= a.size(); k++){
| ~~^~~~~~~~~~~
colouring.cpp:63:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | if (j == a.size() && k == a.size()){
| ~~^~~~~~~~~~~
colouring.cpp:63:40: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | if (j == a.size() && k == a.size()){
| ~~^~~~~~~~~~~
colouring.cpp:82:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for (int i = 0; i <= a.size(); i++) for (int j = 0; j <= a.size(); j++) ans = min(ans, dp[b.size()][i][j]);
| ~~^~~~~~~~~~~
colouring.cpp:82:59: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for (int i = 0; i <= a.size(); i++) for (int j = 0; j <= a.size(); j++) ans = min(ans, dp[b.size()][i][j]);
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
92 ms |
102404 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
161 ms |
102404 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
