Submission #162788

#	Time	Username	Problem	Language	Result	Execution time	Memory
162788		rama_pang	Aliens (IOI16_aliens)	C++14	4 / 100	12 ms	380 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
#define NO_DEBUG
using namespace std;
using lint = long long;
const lint INF = 1e15;

struct Segment {
    lint left, right;

    Segment(lint l = 0, lint r = 0): left(l), right(r) {}

    bool operator < (const Segment &o) const {
        return left < o.left || (left == o.left && right > o.right);
    }

    bool operator == (const Segment &o) const {
        return left == o.left && right == o.right;
    }

};

int N, K;
vector<Segment> segment;
vector<vector<lint>> memo;

lint cost(int i, int n) {
    lint weight, offset;
    weight = segment[n].right - segment[i].left + 1;
    offset = max(0ll, segment[i - 1].right - segment[i].left + 1);
    return (weight * weight) - (offset * offset);
}

lint dp(int n, int k) {
    if (n == 0) 
        return 0;
    if (k < 0) 
        return INF;
    if (memo[n][k] != -1) 
        return memo[n][k];

    lint &res = memo[n][k] = INF;

    for (int i = 1; i <= n; i++) 
        res = min(res, dp(i - 1, k - 1) + cost(i, n));
    
    return res;
}

void preprocess() {
    sort(segment.begin(), segment.end());

    vector<Segment> tmp;
    tmp.emplace_back(-1, -1);
    
    for (auto s : segment) {
        Segment overlap = Segment(min(tmp.back().left, s.left), max(tmp.back().right, s.right));
        if (overlap == s) swap(s, tmp.back());
        if (overlap == tmp.back()) continue;
        tmp.emplace_back(s);
    }

    return void((segment = tmp, N = segment.size() - 1, memo.assign(N + 1, vector<lint>(K + 1, -1))));
}

lint take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    N = n, K = k;
    for (int i = 0; i < N; i++) 
        segment.emplace_back(min(r[i], c[i]), max(r[i], c[i]));
    preprocess();

    #ifndef NO_DEBUG
        cerr << "SEGMENTS:\n";
        for (int i = 1; i <= N; i++) cerr << segment[i].left << " " << segment[i].right << "\n";
    #endif
    
    return dp(N, K);
}

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