Submission #708824

#	Time	Username	Problem	Language	Result	Execution time	Memory
708824		konstantys	Sightseeing in Kyoto (JOI22_kyoto)	C++14	100 / 100	141 ms	11376 KiB

kyoto

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#define f first
#define s second
using namespace std;
struct ulamek{
  long long a,b;
};
bool operator== (ulamek a,ulamek b){
  return a.a*b.b==a.b*b.a;
}
bool operator< (ulamek a,ulamek b){
  return a.a*b.b<b.a*a.b;
}
ulamek mul(int a,int b){
  ulamek c;
  c.a=a,c.b=b;
  return c;
}
priority_queue <pair<ulamek,pair<int,int>>> s;
//using namespace std;
long long tab[2][100005];
int kol[2][100005],przed[2][100005];
int h,w;
long long wyn;
bool us[2][100005];
int main(){
  ios_base::sync_with_stdio(0);
  cin>>h>>w;
  for(int i=0;i<h;i++) cin>>tab[0][i];
  for(int i=0;i<w;i++) cin>>tab[1][i];
  przed[0][0]=-1;
  kol[0][h-1]=-1;
  for(int i=1;i<h;i++){
    kol[0][i-1]=i;
    przed[0][i]=i-1;
    s.push({mul(tab[0][i]-tab[0][i-1],1),{i-1,i}});
  }
  przed[1][0]=-1;
  kol[1][w-1]=-1;
  for(int i=1;i<w;i++){
    kol[1][i-1]=i;
    przed[1][i]=i-1;
    s.push({mul(tab[1][i]-tab[1][i-1],1),{1-i,-i}});
  }
  int h2=h,w2=w;
  while(!s.empty()){
    auto i=s.top();
    s.pop();
    int pom=0;
    if(i.s.f<0 || i.s.s<0) i.s.f=-i.s.f,i.s.s=-i.s.s,pom=1;
    if(us[pom][i.s.f] || us[pom][i.s.s]) continue;
    int a=przed[pom][i.s.s],b=kol[pom][i.s.s];
    if(a!=-1) kol[pom][a]=b;
    if(b!=-1) przed[pom][b]=a;
    us[pom][i.s.s]=1;
    if(a!=-1 && b!=-1)
    s.push({mul(tab[pom][b]-tab[pom][a],b-a),{(1-2*pom)*a,(1-2*pom)*b}});
    if(pom==0){
      if(h-1==i.s.s){
        h=i.s.f+1;
        wyn+=tab[1][w-1]*(i.s.s-i.s.f);
      }
    }else{
      if(w-1==i.s.s){
        w=i.s.f+1;
        wyn+=tab[0][h-1]*(i.s.s-i.s.f);
      }
    }
    if(h==1 && w==1) break;
    /*
    cerr<<pom<<" "<<i.s.s<<"\n";
    //pair<ulamek,int> i=* s.rbegin();
    for(int i=0;i<h2;i++) cerr<<us[0][i];
    cerr<<"\n";
    for(int i=0;i<w2;i++) cerr<<us[1][i];
    cerr<<"\n\n";
    // */
  }
  //cerr<<h<<" "<<w<<"\n";
  cout<<wyn<<"\n";
  return 0;
}

Compilation message (stderr)

kyoto.cpp: In function 'int main()':
kyoto.cpp:48:7: warning: unused variable 'h2' [-Wunused-variable]
   48 |   int h2=h,w2=w;
      |       ^~
kyoto.cpp:48:12: warning: unused variable 'w2' [-Wunused-variable]
   48 |   int h2=h,w2=w;
      |            ^~

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60