oj.uz

Submission #468695

# Submission time Handle Problem Language Result Execution time Memory
468695 2021-08-29T11:36:30 Z ivan_tudor Building Bridges (CEOI17_building) C++14
0 / 100
 3000 ms 63032 KB 
#include<bits/stdc++.h>
using namespace std;
struct functie{
  long long a , b;
  long long operator () (long long x) {
    return 1LL * a * x  + b;
  }
  functie(){
    a = 0;
    b = LLONG_MAX;
  }
  functie(long long _a ,long long _b){
    a = _a;
    b = _b;
  }
};
const long long N = 1E5 + 5;
const int VMAX = 1e6 + 5;
functie lichao[4 * VMAX];
void ins(long long nod, long long l, long long r, functie f){
  long long mid = (l + r)/2;
  if(lichao[nod](mid) > f(mid))
    swap(lichao[nod], f);
  if(l == r)
    return;
  if(f(l) < lichao[nod](l))
    ins(2*nod, l, mid, f);
  if(f(r) < lichao[nod](r))
    ins(2*nod + 1, mid + 1, r, f);
}
long long querymin(long long nod, long long l, long long r, long long p){
  if(p < l || r < p)
    return LLONG_MAX;
  long long mid = (l + r)/2;
  long long cans = lichao[nod](p);
  if(l == r)
    return cans;
  if(p <= mid)
    return min(cans, querymin(2*nod, l, mid, p));
  else
    return min(cans, querymin(2*nod + 1, mid + 1, r, p));
}
long long h[N], dp[N], s[N];
int main()
{
  freopen(".in","r",stdin);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  long long n;
  cin>>n;
  for(long long i = 1; i<=n; i++)
    cin>>h[i];
  for(long long i = 1; i<=n; i++){
    cin>>s[i];
    s[i] += s[i - 1];
  }
  dp[1] = 0;
  ins(1, 0, VMAX, {-2 * h[1], 1LL * h[1] * h[1] + dp[1] - s[1]});
  for(long long i = 2; i<=n; i++){
    dp[i] = h[i] * h[i] + s[i - 1] + querymin(1, 0, VMAX, h[i]);
    ins(1, 0, VMAX, {- 2 * h[i], h[i] * h[i] + dp[i] - s[i]});
  }
  cout<<dp[n];
  return 0;
}

Compilation message

building.cpp: In function 'int main()':
building.cpp:46:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |   freopen(".in","r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 40.0

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