Submission #23408

#	Time	Username	Problem	Language	Result	Execution time	Memory
23408		Bruteforceman	Aliens (IOI16_aliens)	C++11	0 / 100	0 ms	197724 KiB

aliens

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

typedef pair <int, int> pii;
vector <pii> range;

bool comp(pii a, pii b) {
    if(a.first == b.first) {
        return a.second > b.second;
    } else {
        return a.first < b.first;
    }
}

long long count(int x, int y) {
    if(x <= y) return 1LL * (y - x + 1) * (y - x + 1);
    return 0;
}

long long dp[5005][5005];


long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
    return 0;

    range.clear();
    for(int i = 0; i < n; i++) {
        int x = min(r[i], c[i]);
        int y = max(r[i], c[i]);
        range.push_back(make_pair(x, y));
    }
    const int inf = 1e8;
    const long long INF = 1e16;

    multiset <int> s;
    vector <pii> sweep;
    for(int i = 0; i < n; i++) {
        sweep.push_back(make_pair(range[i].first, inf));
        sweep.push_back(make_pair(range[i].second, range[i].first));
    }
    sort(sweep.begin(), sweep.end(), comp);
    range.clear();

    for(int i = 0; i < n+n; i++) {
        if(sweep[i].second == inf) {
            s.insert(sweep[i].first);
        } else {
            if(*s.begin() == sweep[i].second) {
                if(s.size() == 1 || *(++s.begin()) != sweep[i].second) range.push_back(pii(sweep[i].second, sweep[i].first));
            }
            s.erase(s.find(sweep[i].second));
        }
    }
    range.push_back(make_pair(-1, -1));
    sort(range.begin(), range.end());
    int sz = range.size() - 1;

    for(int i = 1; i <= sz; i++) {
        dp[i][0] = INF;
        for(int j = 1; j <= k; j++) {
            dp[i][j] = INF;
            for(int l = 1; l <= i; l++) {
                dp[i][j] = min(dp[i][j], dp[l - 1][j - 1] + count(range[l].first, range[i].second) - count(range[l].first, range[l-1].second));
            }
        }
    }
    return dp[sz][k];
}
/*
int main() {
    int n, m, k;
    assert(3 == scanf("%d %d %d", &n, &m, &k));
    std::vector<int> r(n), c(n);
    for (int i = 0; i < n; i++) {
        assert(2 == scanf("%d %d", &r[i], &c[i]));
    }
    long long ans = take_photos(n, m, k, r, c);

    printf("%lld\n", ans);
    return 0;
}
*/

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