oj.uz

Submission #231659

# Submission time Handle Problem Language Result Execution time Memory
231659 2020-05-14T09:46:42 Z kimbj0709 Building Bridges (CEOI17_building) C++14
0 / 100
 57 ms 18288 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 100050
struct Line {
  int m, b;
  int operator()(int 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);
}
int 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);
  cin.tie(0);cout.tie(0);
  for(int i=0;i<maxn*4;i++){
    a[i] = {0,-INT_MAX*100};
  }
  int no_of_input;
  cin >> no_of_input;
  int input;
  int s = 0;
  vector<int> vect1;
  vector<int> vect2;
  vector<int> dp(no_of_input+1,0);
  for(int i=0;i<no_of_input;i++){
    cin >> input;
    vect1.push_back(input);
  }
  for(int i=0;i<no_of_input;i++){
    cin >> input;
    s += input;
    vect2.push_back(input);
  }
 
  s -= vect2[0];
  vect2[0] = 0;
  dp[0] = 0;
  Line temp;
  temp.m = 2*vect1[0];
  temp.b = -(vect1[0]*vect1[0]-vect2[0]);
  insert(0,maxn,temp,0);
  for(int i=1;i<no_of_input;i++){
    //cout << query(0,maxn,vect1[i],0) << endl;
    assert(query(0,maxn,vect1[i],0)!=-INT_MAX*100);
    dp[i] = -query(0,maxn,vect1[i],0)-vect2[i]+vect1[i]*vect1[i];
    Line temp;
    temp.m = 2*vect1[i];
    temp.b = -(vect1[i]*vect1[i]+dp[i]);
    //cout << temp.m << " " << temp.b << endl;
    insert(0,maxn,temp,0);
  }
  /*for(int i=0;i<no_of_input;i++){
    cout << dp[i] << ' ';
  }
  cout << endl;*/
  cout << dp[no_of_input-1]+s;
}

Compilation message

building.cpp: In function 'int32_t main()':
building.cpp:32:23: warning: integer overflow in expression [-Woverflow]
     a[i] = {0,-INT_MAX*100};
               ~~~~~~~~^~~~
In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from building.cpp:1:
building.cpp:60:46: warning: integer overflow in expression [-Woverflow]
     assert(query(0,maxn,vect1[i],0)!=-INT_MAX*100);
                                      ~~~~~~~~^~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6656 KB Output is correct
2 Runtime error 15 ms 13184 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 9720 KB Output is correct
2 Correct 46 ms 9720 KB Output is correct
3 Correct 45 ms 9712 KB Output is correct
4 Correct 43 ms 9720 KB Output is correct
5 Runtime error 48 ms 18288 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6656 KB Output is correct
2 Runtime error 15 ms 13184 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -