제출 #139820

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
139820		BThero	Aliens (IOI16_aliens)	C++17	4 / 100	71 ms	1532 KiB

aliens

// Why am I so dumb? :c
// chrono::system_clock::now().time_since_epoch().count()

//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "aliens.h"

#define pb push_back
#define mp make_pair

#define all(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << " = " << x << '\n';

#define fi first
#define se second

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;   
typedef pair<int, int> pii;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int MAXN = (int)5e4 + 5;
const int INF = (int)1e9;
const ll LINF = (ll)1e15;

struct Line {
    ll k, b;
    
    Line() {
        k = b = 0ll;
    }
    
    Line(ll k, ll b) : k(k), b(b) {}
    
    ll get(ll x) {
        return k * x + b;
    }
};

double inter(Line a, Line b) {
    return (double)(a.b - b.b) / (double)(b.k - a.k);
}

struct CHT {
    pair<Line, int> H[MAXN];
    int sz, ptr;
    
    CHT() {
        sz = ptr = 0;
    }
    
    bool good(Line a, Line b, Line c) {
        return inter(a, b) < inter(b, c);
    }
    
    void addLine(Line l, int id) {
        while (sz >= 2 && !good(H[sz - 2].fi, H[sz - 1].fi, l)) {
            --sz;
        }
        
        H[sz++] = mp(l, id);
        ptr = min(ptr, sz - 1);
    }
    
    pair<ll, int> query(ll x) {
        while (ptr + 1 < sz && inter(H[ptr].fi, H[ptr + 1].fi) < x) {
            ++ptr;
        }
    
        return mp(H[ptr].fi.get(x), H[ptr].se);
    }
} T;

pair<ll, int> dp[MAXN];

pii arr[MAXN];

int n, m, k;

bool cmp(pii a, pii b) {
    if (a.fi == b.fi) {
        return a.se > b.se;
    }
    
    return a.fi < b.fi;
}

void resolveOverlaps() {
    sort(arr + 1, arr + n + 1, cmp);
    int lim = 0, nn = 0;
    
    for (int i = 1; i <= n; ++i) {
        if (arr[i].se > lim) {
            arr[++nn] = arr[i];
            lim = arr[i].se;
        }
    }
    
    n = nn;
}

ll f(int a, int b) {
    int len = max(0, b - a);
    return len * 1ll * len;
}

pair<ll, int> calc(ll pen) {
    T.sz = 0;
    
    // dp[i] = min(dp[i], dp[j] + (r[i] - l[j])^2 - (r[j + 1] - l[j])^2)
    
    for (int i = 1; i <= n; ++i) {
        Line l(-2 * arr[i].fi, dp[i - 1].fi);
        l.b += arr[i].fi * 1ll * arr[i].fi;
        l.b -= f(arr[i].fi, arr[i - 1].se);
        T.addLine(l, i - 1);
        
        pair<ll, int> tmp = T.query(arr[i].se);
        dp[i].fi = tmp.fi + arr[i].se * 1ll * arr[i].se + pen;
        dp[i].se = dp[tmp.se].se + 1;
    }
    
    return dp[n];
}

ll solve() {
    for (int i = 1; i <= n; ++i) {
        if (arr[i].fi > arr[i].se) {
            swap(arr[i].fi, arr[i].se);
        }
        
        ++arr[i].se;
    }
    
    resolveOverlaps();
    ll ans = LINF;
    
    for (int kk = 1; kk <= k; ++kk) {
        ll l = -INF, r = INF, opt;
        
        while (l <= r) {
            ll mid = (l + r) >> 1;
            pair<ll, int> tmp = calc(mid);
            
            if (tmp.se <= kk) {
                opt = mid;
                r = mid - 1;
            }
            else {
                l = mid + 1;
            }
        }
        
        pair<ll, int> tmp = calc(opt);
        ans = min(ans, tmp.fi - opt * tmp.se);
    }
    
    return ans;
}

ll take_photos(int _n, int _m, int _k, vector<int> r, vector<int> c) {
    n = _n;
    m = _m;
    k = _k;
    
    for (int i = 1; i <= n; ++i) {
        arr[i] = mp(r[i - 1] + 1, c[i - 1] + 1);
    }

    return solve();
}

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

aliens.cpp: In function 'll solve()':
aliens.cpp:160:37: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
         pair<ll, int> tmp = calc(opt);
                                     ^

• Subtask 1: 4 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40