oj.uz

Submission #47847

# Submission time Handle Problem Language Result Execution time Memory
47847 2018-05-08T08:04:33 Z Extazy Building Bridges (CEOI17_building) C++17
30 / 100
 3000 ms 8516 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() && 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++) {
      ans=min(ans,eval(*it,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]);
  }

  printf("%lld\n", dp[1]);

  return 0;
}

Compilation message

building.cpp: In function 'int main()':
building.cpp:98:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
building.cpp:100:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &h[i]);
     ~~~~~^~~~~~~~~~~~~
building.cpp:103: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 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 488 KB Output is correct
5 Correct 2 ms 488 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 842 ms 3956 KB Output is correct
2 Correct 830 ms 5008 KB Output is correct
3 Correct 832 ms 6048 KB Output is correct
4 Correct 237 ms 6824 KB Output is correct
5 Execution timed out 3058 ms 8516 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 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 488 KB Output is correct
5 Correct 2 ms 488 KB Output is correct
6 Correct 842 ms 3956 KB Output is correct
7 Correct 830 ms 5008 KB Output is correct
8 Correct 832 ms 6048 KB Output is correct
9 Correct 237 ms 6824 KB Output is correct
10 Execution timed out 3058 ms 8516 KB Time limit exceeded