제출 #1308607

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1308607		nvc2k8	Building Bridges (CEOI17_building)	C++20	100 / 100	45 ms	9668 KiB

building

#include <bits/stdc++.h>
#define TASK "build"
#define endl mmm
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define BIT(i,x) (((i)>>(x))&1)
#define FOR(i,a,b) for(int i = (a); i<=(b); i++)
#define FORD(i,a,b) for(int i = (a); i>=(b); i--)
#define all(C) (C).begin(), (C).end()
using namespace std;
using ll = long long;
using pii = pair<int,int>;
const int INT_LIM = 2147483647;
const ll LL_LIM = 9223372036854775807;
template <typename X> bool minimize(X &x, const X &y) {if (x>y){x = y; return true;}return false;}
template <typename X> bool maximize(X &x, const X &y) {if (x<y){x = y; return true;}return false;}
///------------------------------------------///
const int maxn = 1e5+5;

struct Line{
    ll a,b;
    Line (ll a = 0, ll b = LL_LIM): a(a), b(b) {}
    ll eval(ll x)
    {
        return a*x+b;
    }
};

struct lichaotree{
    struct node{
        Line line;
        node *left, *right;
        node()
        {
            line = Line();
            left = right = NULL;
        }
    };

    node *root = new node();

    void init()
    {
        root = new node();
    }

    void update(Line line, node *cur, int l = 0, int r = 1e6)
    {
        int mid = (l+r)>>1;
        if (line.eval(mid)<cur->line.eval(mid)) swap(cur->line, line);
        if (l==r) return;
        if (line.a<cur->line.a)
        {
            if (!cur->right) cur->right = new node();
            update(line, cur->right, mid+1, r);
        }
        if (line.a>cur->line.a)
        {
            if (!cur->left) cur->left = new node();
            update(line, cur->left, l, mid);
        }
    };

    ll get(ll x, node *cur, int l = 0, int r = 1e6)
    {
        ll ret = cur->line.eval(x);
        if (l==r) return ret;
        int mid = (l+r)>>1;
        if (x>mid && cur->right) minimize(ret, get(x, cur->right, mid+1, r));
        if (x<=mid && cur->left) minimize(ret, get(x, cur->left, l, mid));
        return ret;
    }
} tree;

int n;
ll a[maxn];
ll b[maxn];

void inp()
{
    cin >> n;
    FOR(i, 1, n) cin >> a[i];
    FOR(i, 1, n) cin >> b[i];
}

ll f[maxn];

void solve()
{
    ll ansalt = (a[n]-a[1])*(a[n]-a[1]);
    FOR(i, 2, n-1) ansalt+= b[i];

    tree.init();
    tree.update(Line(-2*a[1], 0), tree.root);

    ll ans = LL_LIM;

    FOR(i, 2, n-1)
    {
        f[i] = (a[i]*a[i]*2-b[i])+tree.get(a[i], tree.root);
        minimize(ans, f[i]-2*a[i]*a[n]);
        tree.update(Line(-2*a[i], f[i]), tree.root);
    }

    ans+= a[1]*a[1];
    ans+= a[n]*a[n];
    FOR(i, 2, n-1) ans+= b[i];
    cout << min(ans, ansalt);
}

signed main()
{
    ///--------------------------///
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    if (fopen(TASK".INP","r")!=NULL)
    {
        freopen(TASK".INP","r",stdin);
        freopen(TASK".OUT","w",stdout);
    }
    ///--------------------------///

    int NTEST = 1;
    bool multitest = 0;
    if (multitest) cin >> NTEST;

    while (NTEST--)
    {
        inp();
        solve();
    }

    return 0;
}

///------------------------------------------///

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

building.cpp: In function 'int main()':
building.cpp:119:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |         freopen(TASK".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
building.cpp:120:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |         freopen(TASK".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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