oj.uz

Submission #468696

# Submission time Handle Problem Language Result Execution time Memory
468696 2021-08-29T11:36:45 Z ivan_tudor Building Bridges (CEOI17_building) C++14
100 / 100
 103 ms 66424 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;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 62924 KB Output is correct
2 Correct 34 ms 62828 KB Output is correct
3 Correct 32 ms 62920 KB Output is correct
4 Correct 33 ms 62892 KB Output is correct
5 Correct 36 ms 62936 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 65212 KB Output is correct
2 Correct 88 ms 65420 KB Output is correct
3 Correct 85 ms 65432 KB Output is correct
4 Correct 83 ms 65476 KB Output is correct
5 Correct 75 ms 65504 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 62924 KB Output is correct
2 Correct 34 ms 62828 KB Output is correct
3 Correct 32 ms 62920 KB Output is correct
4 Correct 33 ms 62892 KB Output is correct
5 Correct 36 ms 62936 KB Output is correct
6 Correct 103 ms 65212 KB Output is correct
7 Correct 88 ms 65420 KB Output is correct
8 Correct 85 ms 65432 KB Output is correct
9 Correct 83 ms 65476 KB Output is correct
10 Correct 75 ms 65504 KB Output is correct
11 Correct 94 ms 65964 KB Output is correct
12 Correct 92 ms 66168 KB Output is correct
13 Correct 75 ms 66268 KB Output is correct
14 Correct 92 ms 66424 KB Output is correct
15 Correct 78 ms 66116 KB Output is correct
16 Correct 77 ms 66172 KB Output is correct
17 Correct 61 ms 66308 KB Output is correct
18 Correct 61 ms 66244 KB Output is correct