oj.uz

Submission #231645

# Submission time Handle Problem Language Result Execution time Memory
231645 2020-05-14T09:31:54 Z kimbj0709 Building Bridges (CEOI17_building) C++14
30 / 100
 46 ms 9336 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long long
#define maxn 100050
struct Line {
    ld m, b;
    ld operator()(ld x) { return m * x + b; }
  } a[maxn * 4];

  void insert(int l, int r, Line seg, int o) {
    if(l + 1 == r) {
      if(seg(l) > a[o](l)) a[o] = seg;
      return;
    }
    int mid= (l + r) >> 1, lson = o * 2 + 1, rson = o * 2 + 2;
    if(a[o].m > seg.m) swap(a[o], seg);
    if(a[o](mid) < seg(mid)) {
      swap(a[o], seg);
      insert(l, mid, seg, lson);
    }
    else insert(mid, r, seg, rson);
  }
  ld query(int l, int r, int x, int o) {
    if(l + 1 == r) return a[o](x);
    int mid = (l + r) >> 1, lson = o * 2 + 1, rson = o * 2 + 2;
    if(x < mid) return max(a[o](x), query(l, mid, x, lson));
    else return max(a[o](x), query(mid, r, x, rson));
  }
int32_t main(){
  ios::sync_with_stdio(0);
  int n;
  for(int i=0;i<4*maxn;i++){
      a[i] = {-0,-LLONG_MAX};
  }
  cin >> n;
  int input;
  vector<int> vect1,vect2;
  for(int i=0;i<n;i++){
    cin >> input;
    vect1.push_back(input);
  }
  for(int i=0;i<n;i++){
    cin >> input;
    vect2.push_back(input);
  }
  vect2[0] = 0;
  for(int i=1;i<n;i++){
    vect2[i] += vect2[i-1];
  }
  vector<int> dp(n,0);
  insert(0,n,{2*vect1[0],-vect1[0]*vect1[0]},0);
  for(int i=1;i<n;i++){
    dp[i] = -query(0,n,vect1[i],0)+vect2[i-1]+vect1[i]*vect1[i];
    insert(0,n,{2*vect1[i],-dp[i]+vect2[i]-vect1[i]*vect1[i]},0);
  }
  cout << dp[n-1];
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6656 KB Output is correct
2 Incorrect 8 ms 6656 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 9328 KB Output is correct
2 Correct 45 ms 9336 KB Output is correct
3 Correct 46 ms 9328 KB Output is correct
4 Correct 42 ms 9336 KB Output is correct
5 Correct 44 ms 9328 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6656 KB Output is correct
2 Incorrect 8 ms 6656 KB Output isn't correct
3 Halted 0 ms 0 KB -