Submission #1071834

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071834		TheQuantiX	Aliens (IOI16_aliens)	C++17	16 / 100	537 ms	62116 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;

bool comp(pair<ll, ll> a, pair<ll, ll> b) {
    return a.first + a.second < b.first + b.second;
}

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< pair<ll, ll> > st;
    for (int i = 0; i < n; i++) {
        st.insert({min(r[i], c[i]), max(r[i], c[i])});
    }
    vector< pair<ll, ll> > v;
    for (auto i : st) {
        bool fl = 1;
        for (auto j : st) {
            if (i != j && i.first >= j.first && i.second <= j.second) {
                fl = 0;
                break;
            }
        }
        if (fl) {
            v.push_back(i);
        }
    }
    sort(v.begin(), v.end(), comp);
    n = v.size();
    k = min(k, n);
    ll num = 0;
    set< pair<ll, ll> > st1;
    for (int e = 0; e < n; e++) {
        num += (v[e].second - v[e].first + 1) * (v[e].second - v[e].first + 1);
        for (int i = v[e].first; i <= v[e].second; i++) {
            for (int j = v[e].first; j <= v[e].second; j++) {
                st1.insert({i, j});
            }
        }
    }
    num -= st1.size();
    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 {
                ll num1 = 0;
                for (int j1 = j; j1 >= 1; j1--) {
                    if (j1 != j) {
                        num1 += max(0LL, v[j1 - 1].second - v[j - 1].first + 1) * max(0LL, v[j1 - 1].second - v[j - 1].first + 1);
                    }
                    // cout << i << ' ' << j << ' ' << j1 << ' ' << num1 << '\n';
                    dp[i][j] = min(dp[i][j], (v[j - 1].second - v[j1 - 1].first + 1) * (v[j - 1].second - v[j1 - 1].first + 1) + dp[i - 1][j1 - 1] + num1);
                }
            }
        }
    }
    // cout << num << '\n';
    return dp[k][n] - num;
}

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