제출 #141453

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
141453		12tqian	Building Bridges (CEOI17_building)	C++14	100 / 100	74 ms	9084 KiB

building

#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

const double PI = 4 * atan(1);

#define sz(x) (int)(x).size()
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair <int, int>
#define vi vector<int>
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define vpi vector<pair<int, int>>
#define vpd vector<pair<double, double>>
#define pd pair<double, double>

#define f0r(i,a) for(int i=0;i<a;i++)
#define f1r(i,a,b) for(int i=a;i<b;i++)
#define trav(a, x) for (auto& a : x)

void fast_io(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
}
void io(string taskname){
    string fin = taskname + ".in";
    string fout = taskname + ".out";
    const char* FIN = fin.c_str();
    const char* FOUT = fout.c_str();
    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);
    fast_io();
}
const int MAX = 1e5 + 5;
vector<ll> h;
vector<ll> w;
ll pre[MAX];
ll dp[MAX];
#define MAXLC 1000000000
#define INF (1LL<<60)

inline long long f(long long m, long long b, int x) {
	return m * x + b;
}

struct lc_node {
	long long m = 0, b = INF;
	lc_node *l = nullptr, *r = nullptr;

	~lc_node() { delete l; delete r; }

	void add_line(long long nm, long long nb, int lo=0, int hi=MAXLC) {
		int mid = (lo + hi) / 2;
		bool bl = f(nm, nb, lo) < f(m, b, lo);
		bool bm = f(nm, nb, mid) < f(m, b, mid);
		bool bh = f(nm, nb, hi) < f(m, b, hi);
		if (bm) {
			swap(nm, m);
			swap(nb, b);
		}
		if (lo == hi || nb == INF)
			return;
		else if (bl != bm) {
			if (!l) l = new lc_node;
			l->add_line(nm, nb, lo, mid - 1);
		}
		else if (bh != bm) {
			if (!r) r = new lc_node;
			r->add_line(nm, nb, mid + 1, hi);
		}
	}

	long long get(int x, int lo=0, int hi=MAXLC) {
		int mid = (lo + hi) / 2;
		long long ret = f(m, b, x);
		if (l && x < mid)
			ret = min(ret, l->get(x, lo, mid - 1));
		if (r && x > mid)
			ret = min(ret, r->get(x, mid + 1, hi));
		return ret;
	}

	void clear() {
		delete l; delete r;
		m = 0, b = INF, l = nullptr, r = nullptr;
	}

} lc;
int main(){
    fast_io();
    int n;
    cin >> n;
    f0r(i, n){
        int hi;
        cin >> hi;
        h.eb(hi);
    }
    f0r(i, n){
        int wi;
        cin >> wi;
        w.eb(wi);
        if(i == 0) pre[i] = wi;
        else pre[i] = pre[i-1] + wi;
    }
    f0r(i, n){
        if(i == 0){
            lc.add_line(-2*h[i], dp[i] + h[i]*h[i] - pre[i]);
        }
        else{
            dp[i] = lc.get(h[i]) + h[i]*h[i] + pre[i-1];
            lc.add_line(-2*h[i], dp[i] - pre[i] + h[i]*h[i]);
        }
    }
    cout << dp[n-1] << endl;
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

building.cpp:1:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")
 
building.cpp: In function 'void io(std::__cxx11::string)':
building.cpp:47:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen(FIN, "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~
building.cpp:48:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen(FOUT, "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~

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