Submission #309680

#	Time	Username	Problem	Language	Result	Execution time	Memory
309680		phathnv	Aliens (IOI16_aliens)	C++11	60 / 100	2025 ms	6236 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct segment{
    int l, r;
    segment(int _l, int _r){
        l = _l;
        r = _r;
    }
};

int n, m, k;
vector <segment> segs;
vector <vector <ll> > dp;

void prepare(){
    sort(segs.begin(), segs.end(), [](const segment &a, const segment &b){
        if (a.l != b.l)
            return a.l < b.l;
        return a.r > b.r;
    });

    vector <segment> tmp;
    int maxR = -1;
    for(segment s : segs){
        if (s.r > maxR)
            tmp.push_back(s);
        maxR = max(maxR, s.r);
    }
    segs = tmp;
    n = segs.size();
}

ll cost(int l, int r){
    assert(l <= r || l > 0);
    int w = segs[r].r - segs[l].l + 1;
    int intersect = max(0, segs[l - 1].r - segs[l].l + 1);
    return (ll) w * w - (ll) intersect * intersect;
}

void calc(int id, int l, int r, int from, int to){
    if (l > r)
        return;

    int mid = (l + r) >> 1;
    int pos = -1;
    dp[id][mid] = 2e18;
    for(int i = from; i <= min(mid, to); i++)
        if (dp[id][mid] > dp[id ^ 1][i - 1] + cost(i, mid)){
            dp[id][mid] = dp[id ^ 1][i - 1] + cost(i, mid);
            pos = i;
        }
    calc(id, l, mid - 1, from, pos);
    calc(id, mid + 1, r, pos, to);
}

ll solve(){
    segs.insert(segs.begin(), segment(-1, -1));
    dp.resize(2, vector<ll>(n + 2, 2e18));
    dp[0][0] = dp[1][0] = 0;
    for(int i = 1; i <= n; i++)
        dp[1][i] = cost(1, i);

    for(int i = 2; i <= k; i++)
        calc(i & 1, 1, n, 1, n);

    return dp[k & 1][n];
}

ll take_photos(int _n, int _m, int _k, vector<int> r, vector<int> c){
    n = _n;
    m = _m;
    k = _k;
    for(int i = 0; i < n; i++)
        segs.push_back(segment(min(r[i], c[i]), max(r[i], c[i])));

    prepare();
    return solve();
}

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