#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
struct segTree{
vector<ll> v, upd;
int sz;
void init(int n){
sz = 1;
while(sz < n) sz *= 2;
v.assign(2 * sz, INF);
upd.assign(2 * sz, 0);
}
void set(int l, int r, ll val, int x, int lx, int rx){
if(lx >= l && rx <= r){
upd[x] += val;
v[x] += val;
return;
}else if(lx >= r || rx <= l) return;
int m = (lx + rx) / 2;
set(l, r, val, 2 * x + 1, lx, m);
set(l, r, val, 2 * x + 2, m, rx);
v[x] = min(v[2 * x + 1], v[2 * x + 2]) + upd[x];
}
void set(int l, int r, ll val){
set(l, r, val, 0, 0, sz);
}
ll calc(int l, int r, int x, int lx, int rx){
if(lx >= l && rx <= r) return v[x];
else if(lx >= r || rx <= l) return 1e18;
int m = (lx + rx) / 2;
ll c1 = calc(l, r, 2 * x + 1, lx, m);
ll c2 = calc(l, r, 2 * x + 2, m, rx);
return min(c1, c2) + upd[x];
}
ll calc(int l, int r){
return calc(l, r, 0, 0, sz);
}
};
ll getSum(int l, int r, vector<ll>& pre){
if(l > r) return 0;
if(l > 0) return pre[r] - pre[l-1];
else return pre[r];
}
ll solve(int n, int m, vector<int>& down, vector<int>& up){
// cout << "Down:\n";
// for(int x : down) cout << x << " ";
// cout << "\n";
// cout << "Up:\n";
// for(int x : up) cout << x << " ";
// cout << "\n";
segTree st; st.init(m);
vector<ll> pre(n+m-1);
pre[0] = up[0];
for(int i = 1; i < n+m-1; i++){
pre[i] = pre[i-1] + up[i];
//Em guardo el prefix dels costs dels ups, per poder calcular quant he de pagar
//per cada down.
}
ll sum = 0;
for(int i = m-1; i >= 0; i--){
//Itero sobre els downs, i miro quant he de pagar aquest és l'últim que coloco.
sum += down[i];
int s1 = m-i-1 + 1;
int s2 = m-i-1 + (m-1 - (m-1-i)) * 2 - 1;
st.set(m-1-i, m-i, -INF);
if(i == 0) st.set(m-1-i, m-i, sum); //No hi ha rang d'up entre mig si ja estic a la cantonada.
else st.set(m-1-i, m-i, sum + getSum(s1, s2, pre)); //Considero el rang d'ups que he de pagar.
// cout << "s1 " << s1 << " s2 " << s2 << " sum " << sum << " getSum " << getSum(s1, s2, pre) << "\n";
// cout << "i " << i << " col " << m-1-i << " " << m - i << " calc "<< st.calc(m-1-i, m-i) << "\n";
}
sum = 0;
for(int i = m; i < n+m-1; i++){
//Ara considero les down de la meitat inferior de la graella. Inicialment
//coloco totes i després trec poc a poc i calculo la resposta en cada moment.
sum += down[i];
}
// cout << pre.back() << " sum " << sum << " st.v[0] "<< st.v[0] << "\n";
ll ans = min(pre.back(), sum + st.v[0]);
//Casos inicials: totes son ups o coloco totes les down de la meitat inferior i el millor de la
//meitat superior.
//A partir d'ara, com no totes són ups, la diagonal cap abaix que surt de (0, 0) sempre està
//inclosa.
for(int i = n+m-2; i >= m; i--){
//Vaig eliminant downs des de la casella inferior esquerra fins a la que surt de
//(0, 0) (que mai l'arribaré a eliminar).
sum -= down[i]; //Resto aquest cost.
//Quan faig up, es conserva la suma. Per tant, jo vull veure a quina cel·la de la forma
//(0, x) correspon (y, 0). -> x = y.
int col1 = i-m+1; //Perquè la row és i-m+1.
//Quan faig up, es conserva la suma. Per tant, jo vull veure a quina cel·la de la forma
//(0, x) correspon (n-1, y). -> x = y+n-1.
int y = n+m-2-i;
int col2 = y+n-1;
//Si col >= m, realment no estaràn a la fila 0, sino a la columna m-1, però em serveix
//igual per saber l'índex de l'up.
ll cost1 = up[col1];
ll cost2 = up[col2];
if(col1 == col2) cost2 = 0; //La cantonada la contava dos cops.
sum += cost1 + cost2; //Sumo el cost de les dues graelles a columna 0 i fila n-1 que ja no cobreixo.
//Ara al segment tree, he de descomptar als que inclouen aquests ups en la seva suma.
//Vull veure quina és la cel·la de la fila 0 amb la que comparteixen down.
int c1, c2;
if(col1 >= m){
// cout << "here1" << endl;
c1 = m-1 - (col1 - (m-1));
}else c1 = col1;
if(col2 >= m){
// cout << "here2" << endl;
c2 = m-1 - (col2 - (m-1));
}else c2 = col2;
st.set(0, c1, -cost1); //No inclou c1, perquè és obert en r.
st.set(0, c2, -cost2);
// cout << "i " << i << " c1 " << c1 << " c2 " << c2 << " col1 " << col1 << " col2 " << col2 << " sum " << sum << " v[0] " << st.v[0] << "\n";
// cout << "Fila baix col "<< y << " col0 row " << i-m+1 << "\n";
ans = min(ans, sum + st.v[0]);
}
// cout << "Ans " << ans << "\n";
return ans;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
/*
Detall que no havia considerat. Realment, quan deixo de posar una down, i omplo amb ups, no estic
omplint totes les caselles, només les de mateixa paritat, és una mica liada. Però, com les diagonals
només cobreixen caselles de mateixa paritat, realment no és un problema, perquè vol dir que colorejar
les caselles parelles i imparelles són dos problemes independents i puc fer el que tenia dos cops.*/
int n, m; cin >> n >> m;
vector<int> down(n+m-1);
for(auto &i : down) cin >> i;
vector<int> up(n+m-1);
for(auto &i : up) cin >> i;
vector<int> downOdd(n+m-1, 0), downEven(n+m-1, 0);
int odd = (m-1)%2;;
for(int i = 0; i < n + m - 1; i++){
if(odd) downOdd[i] = down[i];
else downEven[i] = down[i];
odd ^= 1;
}
vector<int> upOdd(n+m-1, 0), upEven(n+m-1, 0);
for(int i = 0; i < n + m - 1; i++){
if(i%2) upOdd[i] = up[i];
else upEven[i] = up[i];
}
ll ans = solve(n, m, downOdd, upOdd) + solve(n, m, downEven, upEven);
cout << ans << "\n";
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
94 ms |
33840 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
242 ms |
29776 KB |
Output is correct |
| 2 |
Correct |
253 ms |
28788 KB |
Output is correct |
| 3 |
Correct |
255 ms |
28888 KB |
Output is correct |
| 4 |
Correct |
240 ms |
29264 KB |
Output is correct |
| 5 |
Correct |
235 ms |
29444 KB |
Output is correct |
| 6 |
Correct |
239 ms |
26200 KB |
Output is correct |
| 7 |
Correct |
231 ms |
28500 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
