oj.uz

Submission #47861

# Submission time Handle Problem Language Result Execution time Memory
47861 2018-05-08T09:30:02 Z Extazy Building Bridges (CEOI17_building) C++17
30 / 100
 3000 ms 3120 KB 
#include <bits/stdc++.h>
#define endl '\n'
 
using namespace std;
 
const int N = 100007;
const double EPS = 0.0000001;

struct dynamic_convex_hull_trick {
  struct line {
    long long a,b;
    
    line(){}
    line(long long x, long long y): a(x), b(y) {}
 
    bool operator <(const line &x) const {
      return a==x.a ? b<x.b : a<x.a;
    }
  };
 
  struct cross_t {
    double x;
    line l;

    cross_t(){}
    cross_t(double a, line b): x(a), l(b) {}

    bool operator <(const cross_t &a) const {
      return fabs(x-a.x)<=EPS ? false : x<a.x;
    }
  };

  set < line > s;
  set < cross_t > cross_set;

  long long eval(line l, long long x) {
    return l.a*x+l.b;
  }
 
  double cross_x(line l1, line l2) {
    return (double)(l2.b-l1.b)/(double)(l1.a-l2.a);
  }

  void erase_line(set < line >::iterator it) {
    if(it!=s.begin()) {
      cross_set.erase(cross_t(cross_x(*it,*prev(it)),*it));
    }
    if(next(it)!=s.end()) {
      cross_set.erase(cross_t(cross_x(*next(it),*it),*next(it)));
    }
    if(it!=s.begin() && next(it)!=s.end()) {
      cross_set.insert(cross_t(cross_x(*next(it),*prev(it)),*next(it)));
    }
    s.erase(it);
  }

  void erase_line2(set < line >::iterator it) {
    if(prev(it)!=s.begin()) {
      cross_set.erase(cross_t(cross_x(*it,*prev(prev(it))),*it));
    }
    if(next(it)!=s.end()) {
      cross_set.erase(cross_t(cross_x(*next(it),*it),*next(it)));
    }
    if(prev(it)!=s.begin() && next(it)!=s.end()) {
      cross_set.insert(cross_t(cross_x(*next(it),*prev(prev(it))),*next(it)));
    }
    s.erase(it);
  }

  void insert_line(set < line >::iterator it) {
    if(it!=s.begin() && next(it)!=s.end()) {
      cross_set.erase(cross_t(cross_x(*next(it),*prev(it)),*next(it)));
    }
    if(it!=s.begin()) {
      cross_set.insert(cross_t(cross_x(*it,*prev(it)),*it));
    }
    if(next(it)!=s.end()) {
      cross_set.insert(cross_t(cross_x(*next(it),*it),*next(it)));
    }
  }

  void add_line(line l) {
    if(s.find(l)!=s.end()) return;
 
    set < line >::iterator it=s.insert(l).first,it1,it2;

    if(it!=s.begin()) {
      it1=prev(it);
      if(it1->a==it->a) {
        s.erase(it);
        return;
      }
    }

    if(it!=s.end()) {
      it2=next(it);
      if(it->a==it2->a) {
        erase_line2(it2);
        return;
      }
    }

    insert_line(it);

    if(it!=s.begin() && it!=s.end()) {
      it1=prev(it);
      it2=next(it);
 
      if(it2!=s.end()) {
        if(cross_x(*it2,*it1)>=cross_x(*it,*it1)) {
          erase_line(it);
          return;
        }
      }
    }
 
    while(it!=s.begin()) {
      it1=prev(it);
      if(it1==s.begin()) break;
      it2=prev(it1);
 
      if(cross_x(*it2,*it)>=cross_x(*it2,*it1)) {
        erase_line(it1);
        it=s.find(l);
      }
      else {
        break;
      }
    }
 
    while(it!=s.end()) {
      it1=next(it);
      if(it1==s.end()) break;
      it2=next(it1);
      if(it2==s.end()) break;
 
      if(cross_x(*it2,*it)>=cross_x(*it1,*it)) {
        erase_line(it1);
        it=s.find(l);
      }
      else {
        break;
      }
    }
  }
 
  long long get(long long x) {
    long long ans=eval(*s.begin(),x);
    int cnt=0;

    for(set < line >::iterator it=s.begin();it!=s.end() && cnt<10;it++,++cnt) ans=min(ans,eval(*it,x));

    for(set < cross_t >::iterator it=cross_set.begin();it!=cross_set.end();it++) {
      ans=min(ans,eval(it->l,x));
    }
 
    return ans;
  }
};
 
int n,h[N],w[N];
long long s[N];
dynamic_convex_hull_trick cht;
long long dp[N];
 
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int i;
 
  scanf("%d", &n);
  for(i=1;i<=n;i++) {
    scanf("%d", &h[i]);
  }
  for(i=1;i<=n;i++) {
    scanf("%d", &w[i]);
    s[i]=s[i-1]+w[i];
  }
 
  dp[n]=0;
  for(i=n-1;i>=1;i--) {
    cht.add_line(dynamic_convex_hull_trick::line(-2ll*h[i+1],s[i]+h[i+1]*1ll*h[i+1]+dp[i+1]));
    dp[i]=h[i]*1ll*h[i]-s[i]+cht.get(h[i]);
  }

  /*for(i=1;i<=n;i++) {
    printf("dp [ %d ] = %lld\n", i, dp[i]);
  }*/
 
  printf("%lld\n", dp[1]);
 
  return 0;
}

Compilation message

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

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 556 KB Output is correct
3 Correct 2 ms 556 KB Output is correct
4 Correct 3 ms 556 KB Output is correct
5 Correct 3 ms 556 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3043 ms 3120 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 556 KB Output is correct
3 Correct 2 ms 556 KB Output is correct
4 Correct 3 ms 556 KB Output is correct
5 Correct 3 ms 556 KB Output is correct
6 Execution timed out 3043 ms 3120 KB Time limit exceeded
7 Halted 0 ms 0 KB -