Submission #240068

#	Time	Username	Problem	Language	Result	Execution time	Memory
240068		m3r8	Building Bridges (CEOI17_building)	C++14	100 / 100	144 ms	9656 KiB

building

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

#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){
      if(a.m != b.m){
        return a.m > b.m;
      }else{
        if(a.b != b.b){
          return a.b > b.b;
        }else{
          return a.start < b.start;  
        };
      };
    }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, int i){
  flag = 0;
  //printf("%lld %lld\n",m,b);
  line tmp = {m,b,INF,0.0};  
  line perf = {m,b,INF,0.0};
  line perfp;
  line perfn;
  double f1,f2;
  int ttm=0;

  auto it = (hull.insert(tmp)).first;
  auto itn = it;
  auto itp = it;
  auto itpp =it;
  ++itn;
  if(itn != hull.end() && itn->m == tmp.m){
    hull.erase(tmp);  
    return;
  };
  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--;
      if(itpp->m == tmp.m){
        continue;  
      };
      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,int i){
  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;
};

//ll dp[N];

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],0);
  //dp[0] = 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],i) + w[i-1] + h[i] * h[i];  
    /*
    dp[i] = INF;
    for(int j = 0;j<i;j++){
      dp[i] = std::min(dp[i],dp[j] + (h[i]-h[j]) * (h[i]-h[j]) + w[i-1] - w[j]);  
    };
    if(dp[i] != tmp){
      for(auto j: hull){
        printf("%d %lld %lld %f %f\n",i,j.m,j.b,j.start,j.end);  
      };
      printf("tmp: %lld %lld %d %lld %lld\n",tmp,dp[i],i,h[i],qry(h[i],i));
      break;
    };
    */
    insert(-2 * h[i],tmp - w[i] + h[i] * h[i],i);
  };
  //printf("%lld\n",dp[n-1]);
  printf("%lld\n",tmp);
  return 0;  
};

Compilation message (stderr)

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

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