Submission #1232210

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232210		395333em	Aliens (IOI16_aliens)	C++20	0 / 100	579 ms	1708 KiB

aliens

#include <bits/stdc++.h>

#define int long long

using namespace std;

#define pii pair <int, int>
#define emb emplace_back

const int N = 5e4 + 5; // points
const int K = 1e2 + 5; // pics
const int M = 1e6 + 5; // sides

int n, m, k, dp[K][M];
vector <pii> a;

struct segtree {
    int seg[4 * N];
    void build(int l, int r, int i){
        if (l == r) return seg[i] = a[l].first, void();
        int mid = (l + r) / 2;
        build(l, mid, 2 * i), build(mid + 1, r, 2 * i + 1);
        seg[i] = min(seg[2 * i], seg[2 * i + 1]);
    }
    int query(int l, int r, int i, int ll, int rr){
        if (l >= ll && r <= rr) return seg[i];
        if (r < ll || l > rr) return 1e18;
        int mid = (l + r) / 2; 
        return min(query(l, mid, 2 * i, ll, rr), query(mid + 1, r, 2 * i + 1, ll, rr));
    }
} seg;

int take_photos(int32_t nn, int32_t mm, int32_t kk, vector<int32_t> rr, vector<int32_t> cc) {
    a.emb(0, 0);
    n = nn, m = mm, k = kk;
    for (int i = 0; i < n; i++) a.emb(min(rr[i], cc[i]), max(rr[i], cc[i]));
    sort(a.begin() + 1, a.end(), [](const pii &x, const pii &y){
        return x.second < y.second;
    });
    seg.build(1, n, 1);
    // for (int i = 1; i <= n; i++) cout << seg.query(1, n, 1, 1, i) << ", " << a[i].second << "\n";
    for (int i = 1; i <= n; i++) dp[1][i] = (a[i].second - seg.query(1, n, 1, 1, i) + 1) * (a[i].second - seg.query(1, n, 1, 1, i) + 1);
    // for (int i = 1; i <= n; i++) {
    //     for (int j = i; j <= n; j++) {
    //         cout << "[" << i << ", " << j << "] : " << seg.query(1, n, 1, i, j) << "\n";
    //     }
    // }
    for (int i = 2; i <= k; i++) {
        for (int j = i; j <= n; j++) {
            dp[i][j] = 1e18;
            for (int l = i - 1; l < j; l++) {
                // cout << j << ": " << l << ": " << a[j].second << ", " << seg.query(1, n, 1, l + 1, j) << "\n";
                dp[i][j] = min(dp[i][j], dp[i - 1][l] + (a[j].second - seg.query(1, n, 1, l + 1, j) + 1) * (a[j].second - seg.query(1, n, 1, l + 1, j) + 1));
            }
            // cout << "---------\n";
        }
        // cout << "----------------------------------\n";
    }
    int ans = 1e18;
    for (int i = 1; i <= k; i++) ans = min(ans, dp[i][n]);
    return ans;
}


/*
Observe 1:
a point (x, y) can be reduced to an interval [min(x, y), max(x, y)]
*/

/*
DP calc:
dp[i][j] = min area to cover first j points with i pics
dp[i][j] = min(dp[i - 1][k] + area(k + 1, j))
*/

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: 0 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40