oj.uz

Submission #708815

# Submission time Handle Problem Language Result Execution time Memory
708815 2023-03-12T11:43:04 Z konstantys Sightseeing in Kyoto (JOI22_kyoto) C++14
0 / 100
 1 ms 340 KB 
#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),{a,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;
    //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";
  }
  cout<<wyn<<"\n";
  return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -