oj.uz

Submission #47855

# Submission time Handle Problem Language Result Execution time Memory
47855 2018-05-08T09:11:29 Z Extazy Building Bridges (CEOI17_building) C++17
30 / 100
 3000 ms 3708 KB 
#include <bits/stdc++.h>
#define endl '\n'
 
using namespace std;
 
const int N = 100007;
 
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;
    }
  };
 
  set < line > s;
  
  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 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) {
        s.erase(it2);
        return;
      }
    }

    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)) {
          s.erase(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)) {
        s.erase(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)) {
        s.erase(it1);
        it=s.find(l);
      }
      else {
        break;
      }
    }
  }
 
  long long get(long long x) {
    long long ans=numeric_limits < long long >::max();
 
    for(set < line >::iterator it=s.begin();it!=s.end();it++) {
      //if(it!=s.begin()) printf("%.10lf ", cross_x(*prev(it),*it));
      ans=min(ans,eval(*it,x));
    }
    //printf("\n");
 
    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:116:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
building.cpp:118:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &h[i]);
     ~~~~~^~~~~~~~~~~~~
building.cpp:121: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 376 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 2 ms 448 KB Output is correct
5 Correct 2 ms 480 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 935 ms 3028 KB Output is correct
2 Correct 918 ms 3236 KB Output is correct
3 Correct 912 ms 3236 KB Output is correct
4 Correct 246 ms 3236 KB Output is correct
5 Execution timed out 3050 ms 3708 KB Time limit exceeded

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 2 ms 448 KB Output is correct
5 Correct 2 ms 480 KB Output is correct
6 Correct 935 ms 3028 KB Output is correct
7 Correct 918 ms 3236 KB Output is correct
8 Correct 912 ms 3236 KB Output is correct
9 Correct 246 ms 3236 KB Output is correct
10 Execution timed out 3050 ms 3708 KB Time limit exceeded