제출 #1316983

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1316983		FuelTheBurn	Building Bridges (CEOI17_building)	C++20	0 / 100	56 ms	2648 KiB

building

#ifdef __GNUC__  // GCC or Clang pretending to be GCC
#include <bits/stdc++.h>
#pragma GCC optimize("O2,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#endif

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bit>
#include <algorithm> 
#include <unordered_set>
#include <unordered_map>
#include <utility>
#include <numeric> //gcd, lcm
#include <tuple>     
#include <limits>      
using namespace std;
 
//cin.tie(0)->sync_with_stdio(0);
 
using ll = long long;
using ull=unsigned long long;
using ld = long double;
using db = double;
using str = string;
 
#define FOR(i,a,b) for (ll i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (ll i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x) //will not work for bool
#define travBool(a,x) for (auto a: x)
#define print(x) trav(a,x){cout<<a<<" ";}cout<<endl; //will not work for bool
#define printPair(x) trav(a,x){cout<<"{"<<a.first<<" "<<a.second<<"} ";}cout<<endl; //will not work for bool
#define printBool(x) travBool(a,x){cout<<a<<" ";}cout<<endl;
#define print2d(x) trav(a,x){trav(b,a){cout<<b<<" ";}cout<<endl;}
#define print2dPair(x) trav(a,x){printPair(a);}
#define print2dBool(x) trav(a,x){travBool(b,a){cout<<b<<" ";}cout<<endl;}
#define doPrefixSum2d(data, prefixSum,x,y){prefixSum.resize(x,vector<ll>(y,0));F0R(i,x){prefixSum[i][0]=0;}F0R(j,y){prefixSum[0][j]=0;}FOR(i,1,x){FOR(j,1,y){prefixSum[i][j]=data[i][j]+prefixSum[i-1][j]+prefixSum[i][j-1]-prefixSum[i-1][j-1];}}}//x and y are the size of prefixSum and data including the first row of 0s
#define printQueue(q){auto copyOfQ=q;if(copyOfQ.empty()){cout<<"empty";}while(!copyOfQ.empty()){cout<<copyOfQ.front()<<" ";copyOfQ.pop();}cout<<endl;}
#define printPriorityQueue(q){auto copyOfQ=q;if(copyOfQ.empty()){cout<<"empty";}while(!copyOfQ.empty()){cout<<copyOfQ.top()<<" ";copyOfQ.pop();}cout<<endl;}
#define printDeque(q){auto copyOfQ=q;if(copyOfQ.empty()){cout<<"empty";}while(!copyOfQ.empty()){cout<<copyOfQ.front()<<" ";copyOfQ.pop_front();}cout<<endl;}
#define printDequePair(q){auto copyOfQ=q;if(copyOfQ.empty()){cout<<"empty";}while(!copyOfQ.empty()){cout<<"{"<<copyOfQ.front().first<<" "<<copyOfQ.front().second<<"} ";copyOfQ.pop_front();}cout<<endl;}
#define printStack(q){auto copyOfQ=q;if(copyOfQ.empty()){cout<<"empty";}while(!copyOfQ.empty()){cout<<copyOfQ.top()<<" ";copyOfQ.pop();}cout<<endl;} //printed backwards, last in first out occurs first in the print
#define printStackPair(q){auto copyOfQ=q;if(copyOfQ.empty()){cout<<"empty";}while(!copyOfQ.empty()){cout<<copyOfQ.top().f<<","<<copyOfQ.top().s<<" ";copyOfQ.pop();}cout<<endl;} //printed backwards, last in first out occurs first in the print
//stack prints top to bot
#define FILL(x,v) memset(x,v,sizeof(x)) 
#define NEWLINE endl

#define pb push_back
#define pf push_front //for deques
#define rsz resize
#define sz(x) ll(x.size())
#define all(x) begin(x), end(x)
#define f first
#define s second
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
 
const int MOD = 1e9+7; // 998244353; //this is a completely different unrelated prime number
//const __int128 MOD = 13000000000000019; prime number, for hashing shit
const ll INF = 9000000000000000000;//9e18, very close to LLONG_MAX
//LLONG_MAX is 9.22337e+18
const ld PI = acos((ld)-1);
 
bool debug=false;
bool sortDecreasing(const ll& x, const ll& y){// same as greater<int>(), built in c++ comparator
    return x>y;
}
 
bool ckmin(ll& a, ll b){ return b < a ? a = b, true : false; }//returns false if a was unchanged
bool ckmin(int& a, int b){ return b < a ? a = b, true : false; }//returns false if a was unchanged
bool ckmax(ll& a, ll b){ return b > a ? a = b, true : false; }//returns false if a was unchanged
bool ckmax(int& a, int b){ return b > a ? a = b, true : false; }//returns false if a was unchanged
 
template<typename T>
std::pair<T, T> operator+(const std::pair<T, T>& a, const std::pair<T, T>& b) {
    return {a.first + b.first, a.second + b.second};
}
template<typename T>
std::pair<T, T> operator-(const std::pair<T, T>& a, const std::pair<T, T>& b) {
    return {a.first - b.first, a.second - b.second};
}

struct Line {
	mutable ll a, b, p;
	//k is slope, m is y intercept, p is the last x value for which this line is the best
	bool operator<(const Line& o) const { return a < o.a; }
	bool operator<(ll x) const { return p < x; }
};

struct LineContainer : multiset<Line, less<>> {
	// (for doubles, use inf = 1/.0, div(a,b) = a/b)
	static const ll inf = LLONG_MAX;
	ll div(ll a, ll b) { // floored division
		//-7/3 returns -2 but we want it to return -3
		return a / b - ((a ^ b) < 0 && a % b); }
		//if a and b are opposite signs, and a is not divisible by b we need to subtract an extra 1
	bool isect(iterator x, iterator y) {//we assume x has at most the slope of y, x.k <= y.k

		if (y == end()) return x->p = inf, 0;
		if (x->a == y->a) x->p = x->b > y->b ? -inf : inf;
		else x->p = div(y->b - x->b + (y->a)*(y->a) - (x->a)*(x->a), 2*(y->a - x->a));
		//cout<<"the lines "<<x->a<<" "<<x->b<<" "<<x->p<<" and "<<y->a<<" "<<y->b<<" "<<y->p<<" intersect at ";
		//cout<<x->p<<endl;
		return x->p >= y->p; //we should remove y if true
	}
	//given a b c you find intersection of bc and compare with that of ab to see if you should remove b
	void add(ll a, ll b) {
		//cout<<"add "<<a<<" "<<b<<endl;
		auto z = insert({a, b, 0}), y = z++, x = y;
		while (isect(y, z)) z = erase(z);
		//y is the current for the above
		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
		//x is the past, y is the current for above
		while ((y = x) != begin() && (--x)->p >= y->p)
			//y is the past, x is the past past
			isect(x, erase(y));
	}
	ll query(ll x) {
		assert(!empty());
		auto l = *lower_bound(x);
		return (x-l.a)*(x-l.a) + l.b;
	}
};

signed main() {
	ll N; cin>>N;
    LineContainer lc;
    vector<ll> heights;
    vector<ll> costs;
    ll totalC=0;
    for(int i=0;i<N;i++){
    	ll h; cin>>h; heights.pb(h);
    	
    }
    for(int i=0;i<N;i++){
    	ll c; cin>>c; costs.pb(c);
    	totalC+=c;
    }
    lc.add(heights[0],totalC);
	// for(auto line: lc){
	// 	cout<<line.a<<" "<<line.b<<" "<<line.p<<endl;
	// }
    for(int i=1;i<N-1;i++){

    	ll c=lc.query(heights[i]);
    	lc.add(heights[i],c-costs[i]);
    	// for(auto line: lc){
    	// 	cout<<line.a<<" "<<line.b<<" "<<line.p<<endl;
    	// }
    }
    cout<<lc.query(heights[N-1])<<endl;
    

    return 0;
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40