#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6;
vector<int> t(4 * N) , lz(4 * N);
void push(int u){
t[u * 2] += lz[u];
t[u * 2 + 1] += lz[u];
lz[u * 2] += lz[u];
lz[u * 2 + 1] += lz[u];
lz[u] = 0;
}
void make_new(int n){
function<void(int , int , int)> build = [&](int u , int l , int r){
lz[u] = t[u] = 0;
if(l == r) return;
int m = (l + r) / 2;
build(u * 2 , l , m);
build(u * 2 + 1 , m + 1 , r);
};
build(n , 0 , n);
}
void pos_assign(int u , int l , int r , int pos , int val){
if(l == r){
t[u] = val;
return;
}
push(u);
int m = (l + r) / 2;
if(pos <= m) pos_assign(u * 2 , l , m , pos , val);
else pos_assign(u * 2 + 1 , m + 1 , r , pos , val);
t[u] = max(t[u * 2] , t[u * 2 + 1]);
}
void range_add(int u , int l , int r , int L , int R , int val){
if(l > r || r < L || l > R) return;
if(L <= l && r <= R){
t[u] += val;
lz[u] += val;
return;
}
push(u);
int m = (l + r) / 2;
range_add(u * 2 , l , m , L , R , val);
range_add(u * 2 + 1 , m + 1 , r , L , R , val);
t[u] = max(t[u * 2] , t[u * 2 + 1]);
}
int get_max(int u , int l , int r , int L , int R){
if(l > r || r < L || l > R) return 0;
if(L <= l && r <= R) return t[u];
push(u);
int m = (l + r) / 2;
return max(get_max(u * 2 , l , m , L , R) , get_max(u * 2 + 1 , m + 1 , r , L , R));
}
void pos_assign(int pos , int val , int n){
if(pos < 0 || n - 1 < pos) return;
pos_assign(1 , 0 , n , pos , val);
}
void range_add(int l , int r , int val , int n){
if(r < l) return;
range_add(1 , 0 , n , l , r , val);
}
int get_max(int l , int r , int n){
if(r < l) return 0LL;
return get_max(1 , 0 , n , l , r);
}
main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int n , m;cin >> n >> m;
vector<int> d1(N) , d2(N) , sz(N);
vector<int> f[2];
vector<vector<vector<pair<int , int>>>> cost(2 , vector<vector<pair<int , int>>>((N)));
for(int i = 0;i < n + m - 1;i ++){
cin >> d1[i];
f[i % 2].push_back(d1[i]);
if(i < min(n , m)) sz[i] = i + 1;
if(min(n , m) <= i && i < max(n , m)) sz[i] = sz[i - 1];
if(i >= max(n , m)) sz[i] = sz[i - 1] - 1;
}
int parity;
for(int i = 0;i < n + m - 1;i ++){
cin >> d2[i];
int st = abs(m - i - 1);
if(i % 2 == 0) parity = st % 2;
st /= 2;/*
cout << i << " " << st << " " << st + sz[i] - 1 << " " << parity << endl;*/
cost[i % 2][st + sz[i] - 1].push_back({d2[i] , st});
}
int ans = 0;
for(int w = 0;w < 2;w ++){
int par = (parity ^ (w == 1)) , all_cost = 0 , N = (int)f[w].size();/*
cout << "par W: " << w << " par: " << par << endl; */
make_new(N);/*
cout << "SZ: " << N << endl;*/
for(int i = 0;i < N;i ++){
int all = get_max(0 , i - 1 , N);
pos_assign(i , all + f[w][i] , N);
for(int k = 0;k < cost[par][i].size();k ++){
int end = cost[par][i][k].second;
int Cost = -cost[par][i][k].first;
range_add(end , i , Cost , N);
}
all_cost += f[w][i];
}/*
cout << "MN: ";
cout << get_max(0 , N - 1 , N) << endl;*/
ans += all_cost - max(0LL , get_max(0 , N - 1 , N));
}
cout << ans << endl;
}
Compilation message
colouring.cpp:76:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
76 | main(){
| ^~~~
colouring.cpp: In function 'int main()':
colouring.cpp:108:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for(int k = 0;k < cost[par][i].size();k ++){
| ~~^~~~~~~~~~~~~~~~~~~~~
colouring.cpp:101:7: warning: 'parity' may be used uninitialized in this function [-Wmaybe-uninitialized]
101 | int par = (parity ^ (w == 1)) , all_cost = 0 , N = (int)f[w].size();/*
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
102400 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
102400 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
102400 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
102400 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
102400 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
102400 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
102400 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
