Submission #1190441

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190441		ericl23302	Aliens (IOI16_aliens)	C++20	4 / 100	0 ms	328 KiB

aliens

#include "aliens.h"

#include <iostream>
#include <algorithm>
#include <utility>
#include <climits>
#include <set>
using namespace std;
using ll = long long;

ll sq(ll a) {
    return a * a;
}
ll sq(int a) {
    return (ll)(a) * a;
}

ll getArea(pair<ll, ll> a) {
    return sq(a.second - a.first + 1);
}
ll getArea(ll a, ll b) {
    return sq(b - a + 1);
}

ll positiveArea(ll a, ll b) {
    ll sideLength = b - a + 1;
    return (sideLength > 0 ? sq(sideLength) : 0);
}

set<pair<ll, ll>> hull;
vector<pair<ll, ll>> points;
vector<ll> dp_prev, dp_cur;

ll valOnLine(pair<ll, ll> line, ll x) {
    return (line.second - x * line.first);
}

ll query(ll x) {
    while (hull.size() > 1) {
        auto first = hull.begin(), second = next(first);
        if (valOnLine(*first, x) > valOnLine(*second, x)) hull.erase(first);
        else break;
    }
    return valOnLine(*hull.begin(), x);
}

void addLine(ll m, ll c) {
    while (hull.size() > 2) {
        auto last = prev(hull.end());
        ll m1 = -last->first, c1 = last->second;
        ll m2 = -prev(last)->first, c2 = prev(last)->second;

        if ((c - c1) * (m2 - m1) <= (c1 - c2) * (m1 - m)) hull.erase(last);
        else break;
    }
    hull.emplace(-m, c);
}

ll getA(ll j) {
    return (-2 * points[j].first + 2);
}

ll getB(ll j) {
    return (sq(points[j].first - 1) + (j ? dp_prev[j - 1] - positiveArea(points[j].first, points[j - 1].second) : 0));
}

ll take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
    vector<pair<ll, ll>> oriPoints;
    for (ll i = 0; i < n; ++i) {
        if (r[i] > c[i]) swap(r[i], c[i]);
        oriPoints.emplace_back(r[i], c[i]);
    }
    sort(oriPoints.begin(), oriPoints.end());
    
    pair<ll, ll> cur = oriPoints[0];
    for (ll i = 1; i < n; ++i) {
        if (oriPoints[i].first == cur.first) cur.second = max(oriPoints[i].second, cur.second);
        else if (cur.second < oriPoints[i].second) {
            if (cur.first != -1) points.emplace_back(cur);
            cur = oriPoints[i];
        }
    }
    points.emplace_back(cur);
    int newN = points.size();

    dp_prev.assign(newN, LLONG_MAX / 2); dp_prev[0] = 0;
    dp_cur.assign(newN, 0);
    // cout << newN << '\n';

    for (int i = 1; i <= k; ++i) {
        hull.clear();
        addLine(getA(0), getB(0));
        // for (auto &i : hull) cout << i.first << ' ' << i.second << "   ";
        // cout << '\n';
        for (int j = 1; j <= newN; ++j) {
            ll ri = points[j - 1].second;
            dp_cur[j - 1] = sq(ri) + query(ri);
            // cout << j << ' ' << ri;
            if (j < newN) addLine(getA(j), getB(j));
            // cout << '\n';
        }
        dp_prev = dp_cur;
        // for (auto &i : dp_prev) cout << i << ' ';
        // cout << '\n';
    }

    // for (auto &i : hull) cout << i.first << ' ' << i.second << "   ";
    // cout << '\n';

    return dp_prev[newN - 1];
}

Compilation message (stderr)

aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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