Submission #298707

#	Time	Username	Problem	Language	Result	Execution time	Memory
298707		Hideo	Aliens (IOI16_aliens)	C++17	60 / 100	886 ms	129016 KiB

aliens

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

using namespace std;

#define ll long long
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define pl pair < ll, ll >
#define vl vector < ll >

const int N = 5e4 + 7;
const ll INF = 1e18 + 7;

vector < vl > dp;
pl t[N], s[N];

ll rect (ll l, ll r){
    if (l > r)
        return 0LL;
    return (r - l + 1) * (r - l + 1);
}

ll cost (ll j, ll i){
    return rect(s[j].fr, s[i].sc) - rect(s[j].fr, s[j - 1].sc);
}

void divide (int l, int r, int optl, int optr, int j){
    if (l > r)
        return;
    int mid = (l + r) >> 1, opt = 0;
    for (int c = optl; c <= optr; c++){
        if (dp[mid][j] > dp[c - 1][j - 1] + cost(c, mid)){
            dp[mid][j] = min(dp[mid][j], dp[c - 1][j - 1] + cost(c, mid));
            opt = c;
        }
    }
    divide(l, mid - 1, optl, opt, j);
    divide(mid + 1, r, opt, optr, j);
}

bool comp (pl a, pl b){
    if (a.fr == b.fr)
        return a.sc > b.sc;
    return a.fr < b.fr;
}

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
    dp.resize(n + 1);
    for (int j = 0; j <= k; j++)
        dp[0].pb(0);
    for (int i = 1; i <= n; i++){
        dp[i].pb(0);
        for (int j = 1; j <= k; j++)
            dp[i].pb(INF);
    }
    for (int i = 0; i < n; i++)
        t[i + 1] = {min(r[i] + 1, c[i] + 1), max(r[i] + 1, c[i] + 1)};
    sort(t + 1, t + n + 1, comp);
    ll last = 0;
    int x = 0;
    for (int i = 1; i <= n; i++){
        if (t[i].sc > last){
            last = t[i].sc;
            s[++x] = t[i];
        }
    }
    n = x;
    for (int i = 1; i <= n; i++)
        dp[i][1] = cost(1, i);
    for (int j = 2; j <= k; j++)
        divide(1, n, 1, n, j);
    return dp[n][k];
}

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