#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
ll n,m;
ll A[100005],B[100005];
set<ll> lines,cols;
auto comp = [](pair<pll,pll> a, pair<pll,pll> b)
{
return a.first.first*b.first.second<a.first.second*b.first.first;
};
set<pair<pll,pll>,decltype(comp)> setik(comp); /// 0 -> linie, 1 -> coloana
pll getval(ll a,ll b)
{
//assert(b!=0);
if(a==0)
return {0,1};
ll g=__gcd(a,b);
a/=g;
b/=g;
return {a,b};
}
void elimlin(ll poz)
{
auto it=lines.find(poz);
ll st=0,dr=0;
if(it!=lines.begin())
st=*prev(it);
it++;
if(it!=lines.end())
{
dr=(*it);
assert(dr>poz);
}
lines.erase(poz);
if(st!=0)
{
assert(poz>st);
pll val=getval(A[poz]-A[st],poz-st);
setik.erase({val,{poz,0}});
}
if(dr!=0)
{
//assert(poz<dr);
pll val=getval(A[dr]-A[poz],dr-poz);
setik.erase({val,{dr,0}});
}
if(st!=0&&dr!=0)
{
//assert(st<dr);
pll val=getval(A[dr]-A[st],dr-st);
setik.insert({val,{dr,0}});
}
}
void elimcol(ll poz)
{
auto it=cols.find(poz);
ll st=0,dr=0;
if(it!=cols.begin())
st=*prev(it);
it++;
if(it!=cols.end())
{
dr=(*it);
assert(dr>poz);
}
cols.erase(poz);
if(st!=0)
{
assert(st<poz);
pll val=getval(B[poz]-B[st],poz-st);
setik.erase({val,{poz,1}});
}
if(dr!=0)
{
//assert(dr>poz);
pll val=getval(B[dr]-B[poz],dr-poz);
setik.erase({val,{dr,1}});
}
if(st!=0&&dr!=0)
{
//assert(st<dr);
pll val=getval(B[dr]-B[st],dr-st);
setik.insert({val,{dr,1}});
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>A[i];
lines.insert(i);
}
for(int i=1;i<=m;i++)
{
cin>>B[i];
cols.insert(i);
}
ll cnt=2;
ll x=n;
ll y=m;
for(int i=2;i<=n;i++)
setik.insert({{A[i]-A[i-1],1},{i,0}});
for(int i=2;i<=m;i++)
setik.insert({{B[i]-B[i-1],1},{i,1}});
ll ans=0;
while(!setik.empty())
{
auto it=prev(setik.end());
if((*it).second.second==0) /// linie
{
ll poz=(*it).second.first;
if(poz==x)
cnt--;
if(cnt==0)
{
ll aux=*prev(cols.end());
ans+=(y-aux)*A[poz];
y=aux;
cnt=1;
}
elimlin(poz);
}
else /// coloana
{
ll poz=(*it).second.first;
if(poz==y)
cnt--;
if(cnt==0)
{
ll aux=*prev(lines.end());
ans+=(x-aux)*B[poz];
x=aux;
cnt=1;
}
elimcol(poz);
}
}
/*if(lines.size()==2)
ans+=(x-1)*B[1]+(y-1)*A[*prev(lines.end())];
else
ans+=(x-1)*B[*prev(cols.end())]+(y-1)*A[1];*/
ans+=(x-1)*B[1]+(y-1)*A[1];
cout<<ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
600 KB |
Output is correct |
| 2 |
Correct |
0 ms |
600 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Runtime error |
2 ms |
856 KB |
Execution killed with signal 6 |
| 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 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
600 KB |
Output is correct |
| 2 |
Correct |
0 ms |
600 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Runtime error |
2 ms |
856 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
