Submission #240053

#	Time	Username	Problem	Language	Result	Execution time	Memory
240053		m3r8	Building Bridges (CEOI17_building)	C++14	0 / 100	30 ms	3576 KiB

building

#include <stdio.h>
#include <set>

#define ll long long
#define INF 1e9
#define MINF -INF
#define N 100100

int flag;
ll w[N];
ll h[N];

struct line{
  ll m;
  ll b;
  double start;
  double end;
};
struct compare{
  bool operator()(line a, line b){
    if(!flag){
      return a.m > b.m;  
    }else{
      return a.start < b.start;  
    };
  };
};
double is(line a, line b){
  return ((double)(a.b - b.b))/((double)(b.m-a.m));  
};

std::set<line,compare> hull;

void insert(ll m, ll b){
  flag = 0;
  //printf("%lld %lld\n",m,b);
  line tmp = {m,b,0.0,0.0};  
  line perf = {m,b,0.0,0.0};
  line perfp;
  line perfn;
  double f1,f2;
  int ttm;

  auto it = (hull.insert(tmp)).first;
  auto itn = it;
  auto itp = it;
  auto itpp =it;
  ++itn;
  if(itn != hull.end() && itp != hull.begin()){
    double f1 = is(tmp,*itn);
    if(f1 <= itn->start){
      hull.erase(tmp);  
      return;
    };
  };
  if(itp != hull.begin()){
    itp--;
    while(itp != hull.begin()){
      itpp = itp;
      itp--;
      f1 = is(tmp,*itpp);
      f2 = is(tmp,*itp);
      if(f1 > f2){
        ttm = 1;
        break;  
      };
    };
    if(ttm){
      itpp++;  
      itp++;
    };
    hull.erase(itpp,it);
    perf.start = is(tmp,*itp); 
    perfp = *itp;
    perfp.end = perf.start;
    hull.erase(itp);
    hull.insert(perfp);
  }else{
    perf.start = MINF;  
  };

  if(itn != hull.end()){
    itpp = itn;  
    itn++;
    while(itn != hull.end()){
      double f1 = is(*itn,*itpp);
      double f2 = is(tmp,*itn);
      if(f1 > f2)break;
      itpp = itn;
      itn++;
    };
    itn = it;
    itn++;
    hull.erase(itn,itpp);
    perf.end= is(tmp,*itpp);
    perfn = *itpp;
    perfn.start = perf.end;
    hull.erase(itpp);
    hull.insert(perfn);
  }else{
    perf.end = INF;
  };
  hull.erase(tmp);
  hull.insert(perf);
};

ll qry(ll x){
  flag = 1;  
  line tmp = {0,0,(double)x,0};
  auto it = hull.lower_bound(tmp);
  it--;
  flag = 0;
  if(it->start <= x && it->end >= x){
    return it->m * x + it->b;  
  };
  //printf("Error\n");
  return -1;
};



int main(void){
  int n;
  scanf("%d",&n);
  for(int i = 0;i<n;i++){
    scanf("%lld",&h[i]);
  };
  for(int i = 0;i<n;i++){
    scanf("%lld",&w[i]);  
    if(i != 0){
      w[i] += w[i-1];  
    };
  };
  ll tmp = 0;
  insert(-2 * h[0],0 - w[0] + h[0] * h[0]);
  for(int i = 1;i<n;i++){
    /*for(auto j: hull){
      printf("%d %lld %lld %f %f\n",i,j.m,j.b,j.start,j.end);  
    };
    */
    tmp = qry(h[i]) + w[i-1] + h[i] * h[i];  
    //printf("tmp: %lld\n",tmp);
    insert(-2 * h[i],tmp - w[i] + h[i] * h[i]);
  };
  printf("%lld\n",tmp);
  return 0;  
};

Compilation message (stderr)

building.cpp: In function 'int main()':
building.cpp:124:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
   ~~~~~^~~~~~~~~
building.cpp:126:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&h[i]);
     ~~~~~^~~~~~~~~~~~~~
building.cpp:129:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&w[i]);  
     ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40