oj.uz

Submission #478249

# Submission time Handle Problem Language Result Execution time Memory
478249 2021-10-06T17:10:11 Z KLPP Building Bridges (CEOI17_building) C++14
100 / 100
 197 ms 12848 KB 
#include<bits/stdc++.h>

using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
typedef long long lld;
typedef long long ll;

bool query_flag = false;
struct line {
  long long m, c;
  mutable function<const line*()> succ;
  bool operator<(const line& o) const {
    if (!query_flag) return m < o.m;
    const line* s = succ();
    if (!s) return false;
    return (c - s->c) < (s->m - m) * o.m;
  }
};

struct maximum_hull : multiset<line> {
  bool bad(iterator y) {
    auto x = (y == begin()) ? end() : prev(y), z = next(y);
    if (x == end() && z == end()) return false;
    else if (x == end()) return y->m == z->m && y->c <= z->c;
    else if (z == end()) return y->m == x->m && y->c <= x->c;
    else return (x->c - y->c) * (z->m - y->m) >= (y->c - z->c) * (y->m - x->m);
  }
  void insert_line(const long long& m, const long long& c) {
    auto y = insert({ m, c, nullptr });
    y->succ = [=] { return next(y) == end() ? nullptr : &*next(y); };
    if (bad(y)) { erase(y); return; }
    iterator z;
    while ((z = next(y)) != end() && bad(z)) erase(z);
    while (y != begin() && bad(z = prev(y))) erase(z);
  }
  long long eval(long long x) {
    if (empty()) return numeric_limits<ll>::min();
    query_flag = true;
    auto l = *lower_bound({ x, 0, nullptr });
    query_flag = false;
    return l.m * x + l.c;
  }
};
maximum_hull M;
lld DP[1000000];
lld a[1000000];
lld b[1000000];

int main(){
	int n;
	cin>>n;
	rep(i,0,n)cin>>a[i];
	lld sum=0;
	rep(i,0,n)cin>>b[i],sum+=b[i];
	DP[0]=-b[0];
	M.insert_line(2*a[0],-(DP[0]+a[0]*a[0]));
	rep(i,1,n){
		DP[i]=-M.eval(a[i])+a[i]*a[i]-b[i];
		M.insert_line(2*a[i],-(DP[i]+a[i]*a[i]));
	}
	cout<<DP[n-1]+sum<<endl;
	
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 316 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 3720 KB Output is correct
2 Correct 134 ms 3780 KB Output is correct
3 Correct 121 ms 3780 KB Output is correct
4 Correct 95 ms 3588 KB Output is correct
5 Correct 126 ms 5364 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 316 KB Output is correct
6 Correct 105 ms 3720 KB Output is correct
7 Correct 134 ms 3780 KB Output is correct
8 Correct 121 ms 3780 KB Output is correct
9 Correct 95 ms 3588 KB Output is correct
10 Correct 126 ms 5364 KB Output is correct
11 Correct 119 ms 3764 KB Output is correct
12 Correct 105 ms 3764 KB Output is correct
13 Correct 82 ms 3744 KB Output is correct
14 Correct 111 ms 3824 KB Output is correct
15 Correct 197 ms 12848 KB Output is correct
16 Correct 143 ms 5428 KB Output is correct
17 Correct 64 ms 3652 KB Output is correct
18 Correct 62 ms 3604 KB Output is correct