oj.uz

Submission #42852

# Submission time Handle Problem Language Result Execution time Memory
42852 2018-03-05T12:20:30 Z despasito Building Bridges (CEOI17_building) C++14
100 / 100
 201 ms 22916 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T>
using ordered_set = tree<
	T,
	null_type,
	less<T>,
	rb_tree_tag,
	tree_order_statistics_node_update>;

// gives the number of keys with value strictly less than x
#define lesscount(x) order_of_key(x)
// gives the iterator to kth element (starting from 0)
#define kthiterator(x) find_by_order(x)

#define clock_starts() clock_t begin = clock()
#define clock_ends() clock_t end = clock()
#define print_running_time() double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC; \
printf("Elapsed Time : %.10f second(s)\n", elapsed_secs)
#define readfile(s) freopen(s, "r", stdin)
#define writefile(s) freopen(s, "w", stdout)
#define debug(s) cout<< #s <<" = "<< s <<endl
#define all(v) (v).begin(), (v).end()
#define KeepUnique(v) (v).erase( unique(all(v)), v.end() )
#define cin_cout_is_cool ios_base::sync_with_stdio(false); cin.tie(NULL)
#define PrintBinary(n) cout << #n << " = " << bitset<64>(n) << endl
#define MEMSET(a,val) memset(a, val, sizeof a)
#define PB push_back
#define endl '\n'
#define cin(n) scanf("%d", &n)
#define popcount(x) __builtin_popcount((x))
#define popcountll(x) __builtin_popcountll((x))

inline int myrand(int l, int r) {
	int ret = rand(); ret <<= 15; ret ^= rand();
	if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
	return ret;
}
template <typename F, typename S>
ostream& operator << (ostream& os, const pair< F, S>& p) {
    return os<<"(" <<p.first<<", "<<p.second<<")"; }

typedef pair<int, int> ii;
template<typename T> using min_pq =
	priority_queue<T, vector<T>, greater<T> >;

template<typename T>T max(T a_,T b_,T c_) { return max(a_,max(b_,c_)); }
template<typename T>T min(T a_,T b_,T c_) { return min(a_,min(b_,c_)); }
template<typename T>T min(T a_,T b_,T c_, T d_) { return min(min(a_, b_),min(c_,d_)); }
template<typename T>T max(T a_,T b_,T c_, T d_) { return max(max(a_, b_),max(c_,d_)); }

//int dx[] = {-1, +0, +1, +0};
//int dy[] = {+0, +1, +0, -1};

template<typename T> inline T ceil(T num, T d)
{ return (T)(num/d) + (num%d>(T)0 ? (T)1 : (T)0); }
#define block_no(idx) 		(idx/BLOCK_SIZE)
#define block_starting(idx) (block_no(idx)*BLOCK_SIZE)
#define block_ending(idx) 	(min(n, block_no(idx)*BLOCK_SIZE+BLOCK_SIZE-1))
#define block_rank(idx) 	(idx%BLOCK_SIZE)

#define int long long
typedef long long ll;

// does everything for maximums
const ll is_query = LLONG_MIN+1LL;
struct Line {
    ll m, b;
    mutable function<const Line*()> succ;
    bool operator<(const Line& rhs) const {
        if (rhs.b != is_query) return m < rhs.m;
        const Line* s = succ();
        if (!s) return 0;
        ll x = rhs.m;
        return b - s->b < (s->m - m) * x;
    }
};
struct HullDynamic : public multiset<Line> { // will maintain lower hull for maximum
    bool bad(iterator y) {
        auto z = next(y);
        if (y == begin()) {
            if (z == end()) return 0;
            return y->m == z->m && y->b <= z->b;
        }
        auto x = prev(y);
        if (z == end()) return y->m == x->m && y->b <= x->b;
        return 1.0*(x->b - y->b)*(z->m - y->m) >= 1.0*(y->b - z->b)*(y->m - x->m);
    }
    void addline(ll m, ll b) {
        auto y = insert({ -m, -b }); // edit here for minimumns
        y->succ = [=] { return next(y) == end() ? 0 : &*next(y); };
        if (bad(y)) { erase(y); return; }
        while (next(y) != end() && bad(next(y))) erase(next(y));
        while (y != begin() && bad(prev(y))) erase(prev(y));
    }
    ll query(ll x) {
        auto l = *lower_bound((Line) { x, is_query });
        return -(l.m * x + l.b); // edit here for minimums
    }
}cht;

const int maxn = 100010;

int n, pre[maxn], h[maxn], dp[maxn];

inline int sq(int x) {
	return x * x;
}

int32_t main () {
	//readfile("input.in");
	//writefile("output.out");
	cin>>n;
	for(int i=1; i<=n; i++) cin>>h[i];
	for(int i=1; i<=n; i++) cin>>pre[i];
	for(int i=1; i<=n; i++) pre[i] += pre[i-1];
	dp[1] = 0;
	for(int i=2; i<=n; i++) {
		cht.addline(-2*h[i-1], sq(h[i-1])+dp[i-1]-pre[i-1]);
		dp[i] = cht.query(h[i])+pre[i-1]+sq(h[i]);
	}
	cout<<dp[n]<<endl;
	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 464 KB Output is correct
4 Correct 3 ms 612 KB Output is correct
5 Correct 3 ms 612 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 4184 KB Output is correct
2 Correct 121 ms 5136 KB Output is correct
3 Correct 130 ms 6360 KB Output is correct
4 Correct 107 ms 7028 KB Output is correct
5 Correct 124 ms 9844 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 464 KB Output is correct
4 Correct 3 ms 612 KB Output is correct
5 Correct 3 ms 612 KB Output is correct
6 Correct 120 ms 4184 KB Output is correct
7 Correct 121 ms 5136 KB Output is correct
8 Correct 130 ms 6360 KB Output is correct
9 Correct 107 ms 7028 KB Output is correct
10 Correct 124 ms 9844 KB Output is correct
11 Correct 121 ms 9844 KB Output is correct
12 Correct 129 ms 10400 KB Output is correct
13 Correct 96 ms 11284 KB Output is correct
14 Correct 126 ms 12592 KB Output is correct
15 Correct 201 ms 22916 KB Output is correct
16 Correct 121 ms 22916 KB Output is correct
17 Correct 80 ms 22916 KB Output is correct
18 Correct 76 ms 22916 KB Output is correct