Submission #1183721

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183721		ericl23302	Aliens (IOI16_aliens)	C++20	60 / 100	2095 ms	6584 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);
}

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

void compute(int l, int r, int optl, int optr) {
    if (l > r) return;
    int mid = (l + r) / 2;
    pair<ll, int> best = {LLONG_MAX / 2, -1};
    for (int i = optl; i <= min(mid, optr); ++i) {
        best = min(best, {(i ? dp_prev[i - 1] : 0) + getArea(points[i].first, points[mid].second) - (i ? positiveArea(points[i].first, points[i - 1].second) : 0), i});
    }
    dp_cur[mid] = best.first;
    
    compute(l, mid - 1, optl, best.second);
    compute(mid + 1, r, best.second, optr);
}

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);

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

    int newN = points.size();
    dp_prev.assign(newN, LLONG_MAX / 2);
    dp_cur.assign(newN, 0);
    for (int i = 0; i < k; ++i) {
        compute(0, newN - 1, 0, newN - 1);
        dp_prev = dp_cur;
        // for (int i : dp_prev) cout << i << ' ';
        // 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: 12 / 12
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 0 / 40