Submission #309679

#	Time	Username	Problem	Language	Result	Execution time	Memory
309679		phathnv	Aliens (IOI16_aliens)	C++11	41 / 100	2079 ms	7016 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 = -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;
}

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

    dp[0][0] = dp[0][1] = 0;
    pos[n + 1][0] = pos[n + 1][1] = 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--){
            int id = j & 1;
            for(int u = pos[i][id ^ 1]; u <= min(i, pos[i + 1][id]); u++)
                if (dp[i][id] > dp[u - 1][id ^ 1] + cost(u, i)){
                    dp[i][id] = dp[u - 1][id ^ 1] + cost(u, i);
                    pos[i][id] = u;
                }
        }

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

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: 0 / 19
• Subtask 6: 0 / 40