#include <bits/stdc++.h>
using namespace std;
#define int ll
#define ll long long
#define pii pair<ll, ll>
#define f first
#define s second
#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#define pb push_back
#define FOR(i,a,b) for (int i = a; i<b; ++i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) FOR(i,1,n+1)
#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do( T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do( T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBIT
const int maxn = 2e3+5;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int xpos[maxn], ypos[maxn];
int xv[maxn], yv[maxn];
//ll dp[maxn][maxn];
ll bonus = 0;
vector<pii> clean(vector<int> raw, ll oth) {
int smallest = *min_element(ALL(raw));
bonus += smallest * (oth-1);
for (int &y : raw) {
y -= smallest;
}
int n = SZ(raw);
vector<int> prefmin(n+2, inf), sufmin(n+2, inf);
REP(i, n) {
prefmin[i+1] = min(prefmin[i], raw[i]);
}
for (int i = n-2; i>=0; --i) {
sufmin[i] = min(sufmin[i+1], raw[i+1]);
}
vector<pii> re;
REP(i,n) {
if (raw[i] >= prefmin[i] && raw[i] >= sufmin[i]) {
// useless
continue;
}
re.pb({raw[i], i});
}
return re;
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0);
bug(1,2);
int H,W; cin>>H>>W;
int n,m;
{
vector<int> tmp(H);
REP(i,H) cin>>tmp[i];
vector<pii> gx = clean(tmp,W);
n = SZ(gx);
REP(i, n) {
xpos[i] = gx[i].s, xv[i] = gx[i].f;
}
}
{
vector<int> tmp(W);
REP(i,W) cin>>tmp[i];
vector<pii> gy = clean(tmp,H);
m = SZ(gy);
REP(i, m) {
ypos[i] = gy[i].s, yv[i] = gy[i].f;
}
}
bug(n,m);
// memset(dp, 0x3f, sizeof dp);
// dp[0][0] = 0;
//
//
//
// REP(i,n) {
// REP(j,m) {
// if (i) MN(dp[i][j], dp[i-1][j] + yv[j] * (xpos[i] - xpos[i-1]));
// if (j) MN(dp[i][j], dp[i][j-1] + xv[i] * (ypos[j] - ypos[j-1]));
// }
// }
ll walk = 0;
REP(rar, 2){
int goalx=0, goaly = 0;
while (xv[goalx] > 0) ++goalx;
while (yv[goaly] > 0) ++goaly;
// bug(atx, aty);
// int atx = 0, aty = 0;
// while (atx < goalx && aty < goaly) {
// if (abs(xv[atx]-xv[atx+1]) * abs(ypos[aty] - ypos[goaly]) < abs(yv[aty]-yv[aty+1]) * abs(xpos[atx] - xpos[goalx])) {
// walk += xv[atx] * abs(ypos[aty+1] - ypos[aty]);
// ++aty;
// }else{
// walk += yv[aty] * (abs(xpos[atx+1] - xpos[atx]));
// ++atx;
// }
// }
int atx = goalx, aty = goaly;
while (atx >0 || aty >0) {
ll xdist = inf, ydist = inf;
if (aty) xdist = abs(yv[aty]-yv[aty-1]) * abs(ypos[aty] - ypos[0]);
if (atx) ydist = abs(xv[atx]-xv[atx-1]) * abs(xpos[atx] - xpos[0]);
bug(xdist, ydist);
if (xdist < ydist) {
bug(atx, aty);
walk += xv[atx] * abs(ypos[aty-1] - ypos[aty]);
--aty;
}else{
bug(atx, aty);
walk += yv[aty] * (abs(xpos[atx-1] - xpos[atx]));
--atx;
}
}
bug(walk);
reverse(xpos, xpos+n);
reverse(ypos, ypos+m);
reverse(xv, xv+n);
reverse(yv, yv+m);
}
bug(bonus);
cout<<walk+ bonus<<endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
