#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#define int long long
#define pb push_back
#define pii pair<int, int>
#define lin first
#define col second
using namespace std;
const int MAX = 600005;
const int INF = (int)1e18;
int n, m;
int costP[MAX], costS[MAX];
pii stP[MAX], drP[MAX], stS[MAX], drS[MAX];
vector<int> redP, redS, blueP, blueS;
int convRedP[MAX], convRedS[MAX];
int convBlueP[MAX], convBlueS[MAX];
int sumP[MAX], sumS[MAX];
int minP[MAX], minS[MAX];
void buildConv() {
int np = redP.size() - 1, ns = redS.size() - 1;
for ( int i = 1; i <= np; ++i ) {
convRedP[redP[i]] = i;
}
for ( int i = 1; i <= ns; ++i ) {
convRedS[redS[i]] = i;
}
np = blueP.size() - 1, ns = redS.size() - 1;
for ( int i = 1; i <= np; ++i ) {
convBlueP[blueP[i]] = i;
}
for ( int i = 1; i <= ns; ++i ) {
convBlueS[blueS[i]] = i;
}
}
void updStoP_red( int i ) {
int indS = redS[i];
pii st = stS[indS], dr = drS[indS];
int sum = dr.lin + dr.col;
int dpIndex = convRedP[sum - 1];
int sum1 = st.lin + dr.col;
int stIndex = convRedP[sum1 - 1];
minP[dpIndex] = min( minP[dpIndex], minS[i] + sumP[dpIndex] - sumP[stIndex - 1] );
}
void updPtoS_red( int i ) {
int indP = redP[i];
pii st = stP[indP], dr = drP[indP];
int diff = dr.lin - dr.col;
int dpIndex = convRedS[diff + m];
int diff1 = st.lin - st.col;
int stIndex = convRedS[diff1 + m];
minS[dpIndex] = min( minS[dpIndex], minP[i] + sumS[dpIndex] - sumS[stIndex - 1] );
}
int solve_red() {
int np = redP.size() - 1, ns = redS.size() - 1;
for ( int i = 1; i <= np; ++i ) {
sumP[i] = sumP[i-1] + costP[redP[i]];
minP[i] = INF;
}
for ( int i = 1; i <= ns; ++i ) {
sumS[i] = sumS[i-1] + costS[redS[i]];
minS[i] = INF;
}
for ( int i = 0; i <= min(np, ns); ++i ) {
minP[i+1] = min( minP[i+1], minP[i] + costP[redP[i+1]] );
minS[i+1] = min( minS[i+1], minS[i] + costS[redS[i+1]] );
if ( i > 0 ) {
updStoP_red(i);
updPtoS_red(i);
}
}
return min( minP[np], minS[ns] );
}
void updStoP_blue( int i ) {
int indS = blueS[i];
pii st = stS[indS], dr = drS[indS];
int sum = dr.lin + dr.col;
int dpIndex = convBlueP[sum - 1];
int sum1 = st.lin + dr.col;
int stIndex = convBlueP[sum1 - 1];
minP[dpIndex] = min( minP[dpIndex], minS[i] + sumP[dpIndex] - sumP[stIndex - 1] );
}
void updPtoS_blue( int i ) {
int indP = blueP[i];
pii st = stP[indP], dr = drP[indP];
int diff = dr.lin - dr.col;
int dpIndex = convBlueS[diff + m];
int diff1 = st.lin - st.col;
int stIndex = convBlueS[diff1 + m];
minS[dpIndex] = min( minS[dpIndex], minP[i] + sumS[dpIndex] - sumS[stIndex - 1] );
}
int solve_blue() {
int np = blueP.size() - 1, ns = blueS.size() - 1;
for ( int i = 1; i <= np; ++i ) {
sumP[i] = sumP[i-1] + costP[blueP[i]];
minP[i] = INF;
}
for ( int i = 1; i <= ns; ++i ) {
sumS[i] = sumS[i-1] + costS[blueS[i]];
minS[i] = INF;
}
for ( int i = 0; i <= min(np, ns); ++i ) {
minP[i+1] = min( minP[i+1], minP[i] + costP[blueP[i+1]] );
minS[i+1] = min( minS[i+1], minS[i] + costS[blueS[i+1]] );
if ( i > 0 ) {
updStoP_blue(i);
updPtoS_blue(i);
}
}
return min( minP[np], minS[ns] );
}
signed main() {
int d;
cin >> n >> m;
d = n + m - 1;
for ( int i = 1; i <= d; ++i ) {
cin >> costP[i];
int diff = -m + i;
if ( i <= m ) {
stP[i] = {1, 1 - diff};
} else {
stP[i] = {1 + diff, 1};
}
if ( i <= n ) {
drP[i] = {m + diff, m};
} else {
drP[i] = {n, n - diff};
}
}
for ( int i = 1; i <= d; ++i ) {
cin >> costS[i];
int sum = i + 1;
if ( i <= m ) {
stP[i] = {1, sum - 1};
} else {
stP[i] = {sum - m, m};
}
if ( i <= n ) {
drP[i] = {sum - 1, 1};
} else {
drP[i] = {n, sum - n};
}
}
redS.pb(0), redP.pb(0), blueS.pb(0), blueP.pb(0);
if ( m & 1 ) {
for ( int i = 1; i <= d; i += 2 ) {
redS.pb( i );
redP.pb( i );
}
for ( int i = 2; i <= d; i += 2 ) {
blueS.pb( i );
blueP.pb( i );
}
} else {
for ( int i = 1; i <= d; i += 2 ) {
redS.pb( i );
blueP.pb( i );
}
for ( int i = 2; i <= d; i += 2 ) {
blueS.pb( i );
redP.pb( i );
}
}
buildConv();
int a = solve_red();
int b = solve_blue();
cout << a + b;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
190 ms |
22372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
412 ms |
46108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
