oj.uz

답안 #141453

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
141453 2019-08-08T06:09:37 Z 12tqian Building Bridges (CEOI17_building) C++14
100 / 100
 74 ms 9084 KB 
#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;
}

Compilation message

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.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 5000 KB Output is correct
2 Correct 73 ms 4848 KB Output is correct
3 Correct 70 ms 4740 KB Output is correct
4 Correct 68 ms 4588 KB Output is correct
5 Correct 55 ms 5996 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 74 ms 5000 KB Output is correct
7 Correct 73 ms 4848 KB Output is correct
8 Correct 70 ms 4740 KB Output is correct
9 Correct 68 ms 4588 KB Output is correct
10 Correct 55 ms 5996 KB Output is correct
11 Correct 65 ms 4784 KB Output is correct
12 Correct 68 ms 4764 KB Output is correct
13 Correct 56 ms 4708 KB Output is correct
14 Correct 67 ms 4968 KB Output is correct
15 Correct 62 ms 9084 KB Output is correct
16 Correct 56 ms 5972 KB Output is correct
17 Correct 27 ms 4716 KB Output is correct
18 Correct 26 ms 4716 KB Output is correct