Submission #1058738

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058738		Zicrus	Aliens (IOI16_aliens)	C++17	100 / 100	171 ms	14500 KiB

aliens

#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
 
typedef long long ll;

struct parabola {
    ll b, c;
    ll k;
    
    parabola(ll origin, ll b, ll c, ll k) {
        this->b = 2 * (-origin) + b;
        this->c = origin * origin + b * (-origin) + c;
        this->k = k;
    }

    ll eval(ll x) {
        return x * x + b * x + c;
    }

    static ll intersect(parabola &s, parabola &t) {
        // Line root x2
        ll a = s.b - t.b;
        ll b = s.c - t.c;
        return a == 0 ? -1 : (-b) / a;
    }
};
 
ll n, m;
vector<pair<ll, ll>> p;
deque<pair<ll, parabola>> deq; // obsolete from x, parab
 
pair<ll, ll> solve(ll pen) {
    deq.clear();
    vector<ll> dp(n);
    vector<ll> dpK(n);
    dp[0] = (p[0].first + p[0].second + 2 - m) *
            (p[0].first + p[0].second + 2 - m) + pen;
    dpK[0] = 1;
    vector<parabola> idk;
    deq.push_back({m, parabola(p[0].first, 2*abs(p[0].first+p[0].second+2-m), dp[0], dpK[0])});
    idk.push_back(deq.back().second);
    for (int i = 1; i < n; i++) {
        while (deq.front().first <= p[i].first) deq.pop_front();
        ll val = deq.front().second.eval(p[i].first);
        ll k = deq.front().second.k;
        ll nwVal = (p[i].first + p[i].second + 2 - m) *
                   (p[i].first + p[i].second + 2 - m) + dp[i-1] + pen;
        ll subSide = (p[i-1].first + p[i].second + 2 - m);
        ll nwK = dpK[i-1] + 1;
        if (subSide > 0) nwVal -= subSide * subSide;
        if (nwVal < val || (nwVal <= val && nwK <= k)) {
            val = nwVal;
            k = nwK;
            deq.clear();
        }
        dp[i] = val;
        dpK[i] = k;

        parabola parab(p[i].first, 2*abs(p[i].first+p[i].second+2-m), nwVal, nwK);
        idk.push_back(parab);
        if (deq.empty()) {
            deq.push_back({m, parab});
            continue;
        }
        if (parab.eval(m) >= deq.back().second.eval(m)) continue;
        ll validFrom = (deq.size() < 2 ? 0 : deq[deq.size()-2].first);
        ll eval = parab.eval(validFrom);
        ll evalPrev = deq.back().second.eval(validFrom);
        bool disc = eval < evalPrev || (eval <= evalPrev && nwK <= deq.back().second.k);
        while (disc) {
            deq.pop_back();
            if (deq.empty()) break;
            
            validFrom = (deq.size() < 2 ? 0 : deq[deq.size()-2].first);
            eval = parab.eval(validFrom);
            evalPrev = deq.back().second.eval(validFrom);
            disc = eval < evalPrev || (eval <= evalPrev && nwK <= deq.back().second.k);
        }
        if (!deq.empty()) {
            ll x = parabola::intersect(parab, deq.back().second);
            eval = parab.eval(x);
            evalPrev = deq.back().second.eval(x);
            if (eval < evalPrev || (eval <= evalPrev && nwK <= deq.back().second.k)) {
                if (x >= m) continue;
                deq.back().first = x;
            }
            else {
                if (x+1 >= m) continue;
                deq.back().first = x+1;
            }
        }
        deq.push_back({m, parab});
    }

    return {dpK[n-1], dp[n-1]};
}
 
ll take_photos(int n1, int m1, int k, vector<int> r, vector<int> c) {
    // Sort and filter
    n = n1; m = m1;
    vector<pair<ll, ll>> prs(n);
    for (int i = 0; i < n; i++) {
        if (r[i] > c[i]) prs[i] = {r[i], m-1-c[i]};
        else prs[i] = {c[i], m-1-r[i]};
    }
    sort(prs.begin(), prs.end());
    p.clear();
    for (auto &e : prs) {
        while (!p.empty() && p.back().second <= e.second) p.pop_back();
        p.push_back(e);
    }
    n = p.size();
 
    // Solve
    ll left = 0, right = m*m;
    while (left < right) {
        ll mid = (left + right) / 2;
        pair<ll, ll> val = solve(mid);
        if (val.first > k) {
            left = mid + 1;
        }
        else {
            right = mid;
        }
    }
    pair<ll, ll> res = solve(left);
    return res.second - k*left;
}

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