Submission #212139

#	Time	Username	Problem	Language	Result	Execution time	Memory
212139		lyc	Aliens (IOI16_aliens)	C++14	100 / 100	267 ms	6764 KiB

aliens

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

#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
#define SZ(x) ((int)(x).size())

#define SQ(x) ((long long)(x)*(x))

using ii = pair<long long,int>;
using point = array<int,2>;

struct Line {
    int m; long long c; int u;
    ii eval(int x) { return ii((long long)m*x + c, u); }
};

struct ConvexHull {
    deque<Line> dq;
    long double intersect(Line p, Line q) { return (long double)(p.c-q.c)/(q.m-p.m); }
    void add(int m, long long c, int u) {
        Line l = {m,c,u};
        while (SZ(dq) > 1 && intersect(dq[SZ(dq)-1],dq[SZ(dq)-2]) <= intersect(dq[SZ(dq)-1],l))
            dq.pop_back();
        dq.push_back(l);
    }
    ii query(int x) {
        while (SZ(dq) > 1 && dq[0].eval(x) >= dq[1].eval(x)) dq.pop_front();
        return dq[0].eval(x);
    }
};

ii monge(int n, vector<point> p, long long lcost) {
    ii dp = ii(0,0);
    ConvexHull ch;
    RFOR(i,n-1,0){
        // dp[i] = dp[j] + SQ(p[j][1] - p[i][0] + 1) + SQ(max(0,p[j][1] - p[j+1][0] + 1));
        long long overlap = SQ(max(0,p[i][1] - p[i+1][0] + 1));
        ch.add(-2*(p[i][1]+1), dp.first + SQ(p[i][1]+1) - overlap, dp.second);
        dp = ch.query(p[i][0]);
        dp.first += SQ(p[i][0]) + lcost;
        dp.second += 1;
        //cout << "dp " << i << " :: " << dp.first << " " << dp.second << endl;
    }
    return dp;
}

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
    vector<point> p, q;
    FOR(i,0,n-1){
        if (r[i] > c[i]) swap(r[i],c[i]);
        p.push_back(point({r[i],c[i]}));
    }
    sort(p.begin(),p.end(),[](point a, point b) {
            if (a[0] == b[0]) return a[1] > b[1];
            return a[0] < b[0]; });
    for (auto& x : p) {
        if (!q.empty() && x[1] <= q.back()[1]) continue;
        q.push_back(x);
    }
    n = SZ(q), k = min(k,n);
    q.push_back(point({m,m}));
    long long lo = 0, hi = (long long)m*m+1;
    while (hi-lo > 1) {
        long long mid = (lo+hi)/2;
        auto res = monge(n,q,mid);
        if (res.second <= k) hi = mid;
        else lo = mid;
    }
    auto ans = monge(n,q,hi);
    return ans.first - k*hi;
}

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