Submission #309649

#	Time	Username	Problem	Language	Result	Execution time	Memory
309649		phathnv	Aliens (IOI16_aliens)	C++11	0 / 100	1 ms	384 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;

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 = 0;
    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;
}

ll solve(){
    vector <vector <ll> > dp(n + 2, vector<ll>(k + 1, 2e18));
    vector <vector <int> > pos(n + 2, vector<int>(k + 1, 0));
    segs.insert(segs.begin(), segment(-1, -1));

    for(int j = 0; j <= k; j++){
        dp[0][j] = 0;
        pos[n + 1][j] = n;
    }
    for(int i = 1; i <= n; i++){
        pos[i][1] = 1;
        dp[i][1] = cost(1, i);
    }

    for(int j = 2; j <= k; j++)
        for(int i = n; i >= 1; i--)
            for(int u = pos[i][j - 1]; u <= min(i, pos[i + 1][j]); u++)
                if (dp[i][j] > dp[u - 1][j - 1] + cost(u, i)){
                    dp[i][j] = dp[u - 1][j - 1] + cost(u, i);
                    pos[i][j] = u;
                }

    return dp[n][k];
}

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: 0 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40