oj.uz

답안 #1067053

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1067053 2024-08-20T10:17:55 Z vjudge1 Building Bridges (CEOI17_building) C++17
100 / 100
 45 ms 16724 KB 
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pu push_back
#define ll long long
typedef pair <long,long> ii;
const int N=1e6;
long long mod=1e9;
long n,m,k;
long a[N+1],g[N+10];
ll dp[N+1];
ii b[N+10];

struct Line {
	mutable ll k, m, p;
	bool operator<(const Line& o) const { return k < o.k; }
	bool operator<(ll x) const { return p < x; }
};

struct Linecontain : multiset<Line, less<>> {

	static const ll inf = LLONG_MAX;
	ll div(ll a, ll b) {
		return a / b - ((a ^ b) < 0 && a % b); }
	bool isect(iterator x, iterator y) {
		if (y == end()) return x->p = inf, 0;
		if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
		else x->p = div(y->m - x->m, x->k - y->k);
		return x->p >= y->p;
	}
	void add(ll k, ll m) {
	    k=-k;
	    m=-m;
		auto z = insert({k, m, 0}), y = z++, x = y;
		while (isect(y, z)) z = erase(z);
		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
		while ((y = x) != begin() && (--x)->p >= y->p)
			isect(x, erase(y));
	}
	ll query(ll x) {
		assert(!empty());
		auto l = *lower_bound(x);
		return -l.k * x  -l.m;
	}
};
Linecontain lc;
Line l[N+1],s[N+1],S[N+1];
double e[N+1];


void tinh(){
    cin>>n;
    for(long i=1;i<=n;i++) {cin>>b[i].fi;}
    for(int i=1;i<=n;i++) cin>>b[i].se;
    g[n+1]=0;
    for(int i=n;i>=1;i--) {g[i]=g[i+1]+b[i].se;
    }
    k=1;
    /*
    6
    3 8 7 1 6 6
    0 -1 9 1 2 0
    */
    l[1].m=b[1].fi*b[1].fi+g[2];

    l[1].k=-2*b[1].fi;
    lc.add(l[1].k,l[1].m);
    dp[1]=0;
    for(long i=2;i<=n;i++){
        long A=-2*b[i].fi,B=0;
        ll res=lc.query(b[i].fi)+b[i].fi*b[i].fi - g[i];
        dp[i]=res;
        B=dp[i]+g[i+1]+b[i].fi*b[i].fi;
        lc.add(A,B);

     }
    cout<<dp[n];
    }
int main(){
    //freopen("jday.inp","r",stdin);
    //freopen("jday.out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    tinh();
    return 0;

}

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 10588 KB Output is correct
2 Correct 31 ms 10588 KB Output is correct
3 Correct 32 ms 10588 KB Output is correct
4 Correct 24 ms 10588 KB Output is correct
5 Correct 24 ms 11648 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 26 ms 10588 KB Output is correct
7 Correct 31 ms 10588 KB Output is correct
8 Correct 32 ms 10588 KB Output is correct
9 Correct 24 ms 10588 KB Output is correct
10 Correct 24 ms 11648 KB Output is correct
11 Correct 25 ms 10588 KB Output is correct
12 Correct 27 ms 10588 KB Output is correct
13 Correct 20 ms 10588 KB Output is correct
14 Correct 27 ms 10696 KB Output is correct
15 Correct 45 ms 16724 KB Output is correct
16 Correct 23 ms 11864 KB Output is correct
17 Correct 13 ms 10588 KB Output is correct
18 Correct 13 ms 10712 KB Output is correct