Submission #943559

#TimeUsernameProblemLanguageResultExecution timeMemory
943559andrei_boacaSightseeing in Kyoto (JOI22_kyoto)C++17
0 / 100
2 ms856 KiB
#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 = [](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) { bool prost=0; if(st>=poz) prost=1; //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) { 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); if(setik.find({val,{poz,1}})==setik.end()) prost=1; 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; }

Compilation message (stderr)

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;
      |          ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...