제출 #1071790

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1071790		TheQuantiX	Aliens (IOI16_aliens)	C++17	16 / 100	30 ms	1260 KiB

aliens

#include <bits/stdc++.h>
#include "aliens.h"

using namespace std;
using ll = long long;

constexpr ll INF = 1000000000000000000LL;

ll n, m, q, k, x, y, a, b, c;

long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    if (k == n) {
        set< pair<ll, ll> > st;
        for (int e = 0; e < n; e++) {
            for (int i = min(r[e], c[e]); i <= max(r[e], c[e]); i++) {
                for (int j = min(r[e], c[e]); j <= max(r[e], c[e]); j++) {
                    st.insert({i, j});
                }
            }
        }
        return st.size();
    }
    set<ll> st;
    for (int i = 0; i < n; i++) {
        st.insert(r[i]);
    }
    vector<ll> v;
    for (int i : st) {
        v.push_back(i);
    }
    n = v.size();
    k = min(k, n);
    vector< vector<ll> > dp(k + 1, vector<ll> (n + 1, INF));
    for (int i = 0; i <= k; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0) {
                if (j == 0) {
                    dp[i][j] = 0;
                }
            }
            else {
                for (int j1 = 1; j1 <= j; j1++) {
                    dp[i][j] = min(dp[i][j], (v[j - 1] - v[j1 - 1] + 1) * (v[j - 1] - v[j1 - 1] + 1) + dp[i - 1][j1 - 1]);
                }
            }
        }
    }
    return dp[k][n];
}

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