oj.uz

Submission #231505

# Submission time Handle Problem Language Result Execution time Memory
231505 2020-05-13T21:01:58 Z kimbj0709 Building Bridges (CEOI17_building) C++14
0 / 100
 3000 ms 3492 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
deque<pair<int,int> > lines;//lines in form of first*a+b
vector<int> sum;
int no_of_input,a,b,c;
int countt = 0;
double intersection(pair<int,int> a,pair<int,int> b){
  return 1.0*(double)(((double)a.second-(double)b.second)/((double)b.first-(double)a.first));
}
void update(int a,int b){
  pair<int,int> temp = {a,b};
  /*while(lines.size()>=2&&intersection(lines[lines.size()-2],lines[lines.size()-1])>intersection(lines[lines.size()-1],temp)){
    lines.pop_back();
  }*/
  lines.push_front(temp);
  /*cout << "--\n";
  for(auto k:lines){
    cout << k.first << " " << k.second << endl;
  }
  cout << "--\n";*/
  return;
}
int query(int pos){
  int res = 0;
  for(int i=0;i<lines.size();i++){
    res = max(res,lines[i].first*pos+lines[i].second);
  }
  return res;
  int low = 0,high = lines.size()-1;
  while(low!=high){
    int mid = (low+high)/2;
    if(intersection(lines[mid],lines[mid+1])<pos){
      low = mid+1;
    }
    else{
      high = mid;
    }
  }
  return lines[low].first*pos+lines[low].second;
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  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);
  }
  dp[0] = 0;
  update(2*vect1[0],-(vect1[0]*vect1[0]-vect2[0]));
  for(int i=1;i<no_of_input;i++){
    //cout << query(vect1[i]) << " ";
    dp[i] = -query(vect1[i])-vect2[i]+vect1[i]*vect1[i];
    update(2*vect1[i],-(dp[i]+vect1[i]*vect1[i]));
  }
  /*cout << endl;
  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 'long long int query(long long int)':
building.cpp:26:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<lines.size();i++){
               ~^~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Incorrect 6 ms 384 KB Output isn't correct

Subtask #2
0 / 30.0

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

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Incorrect 6 ms 384 KB Output isn't correct