#include <bits/stdc++.h>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");
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 = [](vector<ll> a, vector<ll> b)
{
return a[0]*b[1]<a[1]*b[0];
};
multiset<vector<ll>,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)
{
bool prost=0;
if(st>=poz)
prost=1;
//assert(poz>st);
pll val=getval(A[poz]-A[st],poz-st);
setik.erase({val.first,val.second,poz,0});
}
if(dr!=0)
{
//assert(poz<dr);
pll val=getval(A[dr]-A[poz],dr-poz);
setik.erase({val.first,val.second,dr,0});
}
if(st!=0&&dr!=0)
{
//assert(st<dr);
pll val=getval(A[dr]-A[st],dr-st);
setik.insert({val.first,val.second,dr,0});
}
}
void elimcol(ll poz)
{
bool ok=0;
if(poz==450)
{
//cout<<"a trecut pe aici\n";
ok=1;
}
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)
{
bool prost=0;
if(st>=poz)
prost=1;
//assert(st<poz);
pll val=getval(B[poz]-B[st],poz-st);
setik.erase({val.first,val.second,poz,1});
}
if(dr!=0)
{
//assert(dr>poz);
pll val=getval(B[dr]-B[poz],dr-poz);
setik.erase({val.first,val.second,dr,1});
}
if(st!=0&&dr!=0)
{
//assert(st<dr);
pll val=getval(B[dr]-B[st],dr-st);
setik.insert({val.first,val.second,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++)
{
bool ok=0;
if(i==305)
ok=1;
vector<ll> v={A[i]-A[i-1],1,i,0};
ll val=v[2];
setik.insert({A[i]-A[i-1],1,i,0});
//cout<<i<<": "<<setik.count({33,1,306,0})<<'\n';
}
return 0;
for(int i=2;i<=m;i++)
setik.insert({B[i]-B[i-1],1,i,1});
ll ans=0;
while(lines.size()>=2||cols.size()>=2)
{
bool ok=0;
int lg=(int)lines.size()+(int)cols.size()-2;
int L=setik.size();
if(setik.size()!=(int)lines.size()+(int)cols.size()-2)
ok=1;
assert(!setik.empty());
auto it=prev(setik.end());
if((*it)[3]==0) /// linie
{
ll poz=(*it)[2];
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)[2];
if(poz==y)
cnt--;
if(cnt==0)
{
ll aux=*prev(lines.end());
ans+=(x-aux)*B[poz];
x=aux;
cnt=1;
}
elimcol(poz);
}
}
ans+=(x-1)*B[1]+(y-1)*A[1];
cout<<ans;
return 0;
}
Compilation message
kyoto.cpp: In function 'void elimlin(ll)':
kyoto.cpp:42:14: warning: variable 'prost' set but not used [-Wunused-but-set-variable]
42 | bool prost=0;
| ^~~~~
kyoto.cpp: In function 'void elimcol(ll)':
kyoto.cpp:83:14: warning: variable 'prost' set but not used [-Wunused-but-set-variable]
83 | bool prost=0;
| ^~~~~
kyoto.cpp:64:10: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
64 | bool ok=0;
| ^~
kyoto.cpp: In function 'int main()':
kyoto.cpp:123:14: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
123 | bool ok=0;
| ^~
kyoto.cpp:127:12: warning: unused variable 'val' [-Wunused-variable]
127 | ll val=v[2];
| ^~~
kyoto.cpp:140:24: warning: comparison of integer expressions of different signedness: 'std::multiset<std::vector<long long int>, <lambda(std::vector<long long int>, std::vector<long long int>)> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
140 | if(setik.size()!=(int)lines.size()+(int)cols.size()-2)
| ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
kyoto.cpp:137:14: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
137 | bool ok=0;
| ^~
kyoto.cpp:138:13: warning: unused variable 'lg' [-Wunused-variable]
138 | int lg=(int)lines.size()+(int)cols.size()-2;
| ^~
kyoto.cpp:139:13: warning: unused variable 'L' [-Wunused-variable]
139 | int L=setik.size();
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
