Submission #23417

#	Time	Username	Problem	Language	Result	Execution time	Memory
23417		Bruteforceman	Aliens (IOI16_aliens)	C++11	60 / 100	306 ms	14224 KiB

aliens

#define JUDGE

#ifndef JUDGE
#include "aliens.h"
#endif // JUDGE

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

typedef pair <int, int> pii;
vector <pii> range;
const long long INF = 1e16;

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[2][50005];

vector <long long> M;
vector <long long> C;
int pointer;

bool bad(int x, int y, int z) {
    if(M[y] == M[z]) return true;
    return (C[y] - C[z]) * (M[z] - M[x]) <= (C[x] - C[z]) * (M[z] - M[y]);
}

void addLine(long long m, long long c) {
    if(!M.empty() && M.back() == m && C.back() < c) return ;
    M.push_back(m);
    C.push_back(c);
    while(M.size() >= 3 && bad(M.size() - 3, M.size() - 2, M.size() - 1)) {
        M.erase(M.end() - 2);
        C.erase(C.end() - 2);
    }
}

long long query(long long x) {
    if(M.empty()) return INF;
    if(pointer >= M.size()) {
        pointer = M.size() - 1;
    }
    while(pointer + 1 < M.size() && M[pointer] * x + C[pointer] >= M[pointer + 1] * x + C[pointer + 1]) {
        pointer++;
    }
    return M[pointer] * x + C[pointer];
}


long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
    set <pii> all;
    for(int i = 0; i < n; i++) {
        int x = min(r[i], c[i]);
        int y = max(r[i], c[i]);
        all.insert(make_pair(x, y));
    }

    vector <pii> aux (all.begin(), all.end());

    const int inf = 1e8;

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

    for(int i = 0; i < (int) sweep.size(); 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;

    memset(dp, 0, sizeof dp);
    for(int i = 1; i <= sz; i++) {
        dp[0][i] = INF;
    }
    int ro = 0;
    for(int i = 1; i <= k; i++) {
        ro ^= 1;
        M.clear();
        C.clear();
        pointer = 0;
        for(int j = 1; j <= sz; j++) {
            dp[ro][j] = INF;
            if(dp[ro ^ 1][j - 1] < INF) addLine(-2LL * range[j].first, 1LL * range[j].first * range[j].first + dp[ro ^ 1][j - 1] - count(range[j].first, range[j-1].second));
            dp[ro][j] = min(dp[ro][j], query(range[j].second + 1) + 1LL * (range[j].second + 1) * (range[j].second + 1));
            /*
            for(int l = 1; l <= j; l++) {
                dp[ro][j] = min(dp[ro][j], dp[ro ^ 1][l - 1] + count(range[l].first, range[j].second) - count(range[l].first, range[l-1].second));
                dp[]
            }
            */
        }
    }
    return dp[ro][sz];
}

#ifndef JUDGE
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;
}
#endif // JUDGE

Compilation message (stderr)

aliens.cpp: In function 'long long int query(long long int)':
aliens.cpp:50:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(pointer >= M.size()) {
                ^
aliens.cpp:53:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pointer + 1 < M.size() && M[pointer] * x + C[pointer] >= M[pointer + 1] * x + C[pointer + 1]) {
                       ^

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