This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<iostream>
#include<stdio.h>
#include<stdint.h>
#include<vector>
#include<algorithm>
#include<utility>
#include<set>
#include<map>
#include<queue>
#include<stack>
using namespace std;
const int64_t INF = 1e18;
const int64_t mINF = 1e9;
const int64_t MOD = 998244353;
const int nbit = 11;
const int ndig = 10;
const int nchar = 26;
const int D = 4;
int dr[D] = {0, 1, 0, -1};
int dc[D] = {1, 0, -1, 0};
struct Thing
{
int64_t val;
int i;
int j;
int t;
Thing(int64_t val_, int i_, int j_, int t_) : val(val_), i(i_), j(j_), t(t_) {}
bool operator < (const Thing& o) const
{
int64_t len1 = j - i;
int64_t len2 = o.j - o.i;
if(val * len2 != o.val * len1) return (val * len2) > (o.val * len1);
if(t != o.t) return t > o.t;
if(i != o.i) return i > o.i;
return j > o.j;
}
};
struct Solution
{
int64_t ans;
set<int> ai;
set<int> bi;
set<Thing> s;
vector<int64_t> a;
vector<int64_t> b;
Solution() {}
void solve()
{
int nr;
int nc;
cin >> nr >> nc;
a.resize(nr);
b.resize(nc);
for(int i = 0; i < nr; i++)
{
cin >> a[i];
}
for(int i = 0; i < nc; i++)
{
cin >> b[i];
}
//t = 0 = a // t = 1 = b
for(int i = 1; i < nr; i++)
{
s.insert(Thing(a[i] - a[i - 1], i - 1, i, 0));
}
for(int i = 1; i < nc; i++)
{
s.insert(Thing(b[i] - b[i - 1], i - 1, i, 1));
}
s.insert(Thing(-INF, -1, -2, - 1));
for(int i = 0; i < nr; i++)
{
ai.insert(i);
}
for(int i = 0; i < nc; i++)
{
bi.insert(i);
}
ans = 0;
while((int) s.size() != 1)
{
Thing tmp = *(s.begin());
s.erase(s.begin());
int i = tmp.i;
int j = tmp.j;
int t = tmp.t;
if(t == 1) RemoveCol(i, j);
else RemoveRow(i, j);
}
cout << ans << "\n";
}
void RemoveCol(int i, int j)
{
bi.erase(j);
set<int>::iterator it = bi.lower_bound(j);
if(it != bi.end())
{
int nx = (*it);
s.erase(Thing(b[nx] - b[j], j, nx, 1));
s.insert(Thing(b[nx] - b[i], i, nx, 1));
}
else
{
int len = j - i;
for(int c = 0; c < len; c++)
{
ans += a.back();
b.pop_back();
}
}
}
void RemoveRow(int i, int j)
{
ai.erase(j);
set<int>::iterator it = ai.lower_bound(j);
if(it != ai.end())
{
int nx = (*it);
s.erase(Thing(a[nx] - a[j], j, nx, 0));
s.insert(Thing(a[nx] - a[i], i, nx, 0));
}
else
{
int len = j - i;
for(int c = 0; c < len; c++)
{
ans += b.back();
a.pop_back();
}
}
}
int modsub(int t1, int t2)
{
int res = t1 - t2;
if(res < 0) res += MOD;
return res;
}
int modadd(int t1, int t2)
{
int res = t1 + t2;
if(res >= MOD) res -= MOD;
return res;
}
int modmul(int t1, int t2)
{
int64_t res = 1LL * t1 * t2;
return (res % MOD);
}
bool BIT(int& mask, int& j)
{
return (mask & MASK(j));
}
int MASK(int j)
{
return (1 << j);
}
};
void __startup()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
}
int main()
{
__startup();
int t = 1;
// cin >> t;
for(int i = 1; i <= t; i++)
{
Solution().solve();
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |