제출 #779520

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
779520		vjudge1	Aliens (IOI16_aliens)	C++17	4 / 100	1 ms	340 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<long long, long long>
#define st first
#define nd second
//#define endl "\n"
#define sp " "
#define N 50005
#define ll long long

vector<pii> o;
ll dp[N][105], M;
const ll INF = 2e18 + 7;

ll dist(int x, int y){
    ll h = M - (x + y - 2);
    h = max((ll)0, h);
    return h * h;
}

ll cost(int i, int j){
    if (i > j) swap(i, j);
    pii x = o[i], y = o[j];
    ll prv = 0;
    if (i > 1) prv = dist(max(x.st, o[i - 1].st), max(x.nd, o[i - 1].nd));

    ll curr = dist(min(x.st, y.st), min(x.nd, y.nd)) - prv;
    return curr;
}


void f(int cnt, int l, int r, int sl, int sr){
    if (l > r) return;
    int mid = (l + r) / 2;
    pii best = {INF, INF};
    for (int i = sl; i <= min(sr, mid); i++){
        best = min(best, {cost(i, mid) + dp[cnt - 1][i - 1], i});
    }
    ll opt = best.nd;
    dp[cnt][mid] = best.st;
    f(cnt, l, mid - 1, sl, opt);
    f(cnt, mid + 1, r, opt, sr);
}


long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    vector<pii> p;
    M = m;
    for (int i = 0; i < n; i++)
    {
        r[i]++, c[i]++;
        int tmp = r[i];
        r[i] = c[i];
        c[i] = m - tmp + 1;
        if (r[i] + c[i] > m + 1){
            int tmp = r[i];
            r[i] = m + 1 - c[i];
            c[i] = m + 1 - tmp;
        }
        p.pb({r[i], c[i]});
    }
    sort(p.begin(), p.end());
    pii last = {0, m + 5};
    for (auto i : p){
        if (i.nd < last.nd){
            o.pb(i);
            last = i;
        }
    }
    o.pb({m + 1, 0});
    reverse(o.begin(), o.end());
    int gh = o.size();
    for (int i = 1; i < gh; i++){
        dp[1][i] = cost(1, i);
    }


    for (int i = 2; i <= k; i++)
    {
        f(i, 1, gh - 1, 1, gh - 1);
    }

    return dp[k][o.size() - 1];;
}

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