#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>
#define pb push_back
struct uwu {
int l,r,sz,v;
bool operator<(const uwu &oth) const {
// compare v/sz
// v/sz > oth.v/oth.sz
// v * oth.sz > oth.v * sz
if(v*oth.sz != oth.v*sz) {
return v*oth.sz>oth.v*sz;
}
// this makes high values first so i want l values increasing
return l>oth.l;
}
};
void db(uwu x) {
cout<<x.l<<' '<<x.r<<' '<<x.sz<<' '<<x.v<<endl;
}
int32_t main() {
int h,w; cin>>h>>w;
vi a(h+1); vi b(w+1);
for(int i=1; i<=h; i++) {
cin>>a[i];
}
for(int i=1; i<=w; i++) {
cin>>b[i];
}
set<uwu> A, B;
for(int i=1; i<h; i++) {
A.insert({i, i+1, 1, a[i+1]-a[i]});
}
for(int i=1; i<w; i++) {
B.insert({i, i+1, 1, b[i+1]-b[i]});
}
int ret=0;
vi toA(h+1), toB(w+1);
for(int i=0; i<=h; i++) {
toA[i]=i+1;
}
for(int i=0; i<=w; i++) {
toB[i]=i+1;
}
A.insert({0, 1, 1, (int)-1e9});
B.insert({0, 1, 1, (int)-1e9});
while(A.size()>1 || B.size()>1) {
// cout<<"A, B: ";
// db(*(A.begin())); db(*(B.begin()));
if(*A.begin() < *B.begin()) {
// cout<<"A bigger"<<endl;
uwu rm = *A.begin(); A.erase(A.begin());
if(toA[rm.l]==(int)a.size()-1) {
for(int _=0; _<rm.sz; _++) {
ret+=*(--b.end()); a.pop_back();
}
continue;
}
int nxt1=toA[rm.l]; int nxt2=toB[nxt1];
A.erase({nxt1, nxt2, nxt2-nxt1, a[nxt2]-a[nxt1]});
toA[rm.l]=nxt2;
if(rm.l<=nxt2) A.insert({rm.l, nxt2, nxt2- rm.l, a[nxt2]-a[rm.l]});
// cout<<"insert "<<rm.l<<' '<<nxt2<<' '<<nxt2-rm.l<<' '<<a[nxt2]-a[rm.l]<<endl;
} else {
// cout<<"B bigger"<<endl;
// remove from B
uwu rm = *B.begin(); B.erase(B.begin());
if(toB[rm.l]==(int)b.size()-1) {
// add to answer since we're forced (?)
for(int _=0; _<rm.sz; _++) {
ret+=*(--a.end()); b.pop_back();
}
continue;
}
int nxt1=toB[rm.l]; int nxt2=toB[nxt1];
B.erase({nxt1, nxt2, nxt2-nxt1, b[nxt2]-b[nxt1]}); // erase the next segment
toB[rm.l]=nxt2; // update range
if(rm.l<=nxt2) B.insert({rm.l, nxt2, nxt2-rm.l, b[nxt2]-b[rm.l]}); // add the new segment
// cout<<"insert "<<rm.l<<' '<<nxt2<<' '<<nxt2-rm.l<<' '<<b[nxt2]-b[rm.l]<<endl;
}
}
cout<<ret<<endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Execution timed out |
2055 ms |
348 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
