Submission #170062

#	Time	Username	Problem	Language	Result	Execution time	Memory
170062		osaaateiasavtnl	Aliens (IOI16_aliens)	C++14	100 / 100	358 ms	12020 KiB

aliens

#include<bits/stdc++.h>
#ifdef HOME
#else
#include "aliens.h"
#endif
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define Time (double)clock()/CLOCKS_PER_SEC
bool comp(ii a, ii b) {
    return a.f < b.f || (a.f == b.f && a.s > b.s);
}   
const int N = 1e5 + 7, INF = 1e18 + 7, C = 1e12;

struct Line {
    int a, b, k;
};  
ii get(Line l, int x) {
    return mp(l.a + l.b * x, l.k);
}   
int get_better(Line a, Line b) {
    if (a.a >= b.a)
        return -INF;
    int d = a.b - b.b;
    return (b.a - a.a + d - (a.k >= b.k)) / d;
}   
struct Cht {
    vector <Line> a;
    int ptr;
    void clear() {
        a.clear();
        ptr = 0;                    
    }
    void add(ii l, int k) {
        Line add = {l.f, l.s, k};
        while (a.size() >= 2 && get_better(add, a.back()) <= get_better(a.back(), a[a.size() - 2]))
            a.pop_back();
        while (a.size() && add.a >= a.back().a)
            a.pop_back();
        a.app(add);
    }   
    ii get_cht(int x) {
        if (ptr == a.size())
            return mp(-INF, -INF);
        while (ptr + 1 < a.size() && get(a[ptr + 1], x) > get(a[ptr], x))
            ++ptr;
        return get(a[ptr], x);
    }   
} mem;  

ii dp[N];
ii solve(int n, int sh, vector <ii> &a) {
    dp[0] = mp(0, 0);
    mem.clear();
    for (int i = 1; i <= n; ++i) {        
        if (i == 1 || a[i - 2].s < a[i - 1].f) {
            mem.add(mp(-dp[i - 1].f - a[i - 1].f * a[i - 1].f, 2 * a[i - 1].f), -dp[i - 1].s);  
        }
        else {
            int in = a[i - 2].s - a[i - 1].f + 1;
            mem.add(mp(-dp[i - 1].f - a[i - 1].f * a[i - 1].f + in * in, 2 * a[i - 1].f), -dp[i - 1].s);  
        }   
        dp[i] = mem.get_cht(a[i - 1].s + 1);
        dp[i].f *= -1; dp[i].s *= -1; 
        dp[i].f += (a[i - 1].s + 1) * (a[i - 1].s + 1) + sh;
        dp[i].s += 1;
        /*
        for (int l = 0; l < i; ++l) {
            int tl = a[l].f, tr = a[i - 1].s;
            int len = tr - tl + 1;
            if (l && a[l - 1].s >= tl) {
                int in = a[l - 1].s - tl + 1;
                dp[i] = min(dp[i], mp(dp[l].f + len * len - in * in + sh, dp[l].s + 1));
            }
        }
        */
    }   
    return dp[n];
}   
long long take_photos(signed n, signed m, signed k, vector<signed> rr, vector<signed> cc) {
    vector <ii> a;
    for (int i = 0; i < n; ++i) {
        if (cc[i] < rr[i])
            swap(rr[i], cc[i]);
        a.app(mp(rr[i], cc[i]));
    }
    sort(all(a), comp);
    vector <ii> b;
    int r = -1;
    for (auto e : a) {
        if (e.s <= r) 
            continue;
        b.app(e);
        r = e.s;
    }   
    a = b;
    n = a.size();

    if (k >= n)
        return solve(n, 0, a).f;

    int l = -C;
    r = C;
    while (l < r - 1) {
        int mid = (l + r) / 2;
        if (solve(n, mid, a).s <= k)
            r = mid;
        else
            l = mid;
    }
    auto t = solve(n, r, a);
    return t.f - k * r;
}            

Compilation message (stderr)

aliens.cpp: In member function 'std::pair<long long int, long long int> Cht::get_cht(long long int)':
aliens.cpp:52:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (ptr == a.size())
             ~~~~^~~~~~~~~~~
aliens.cpp:54:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (ptr + 1 < a.size() && get(a[ptr + 1], x) > get(a[ptr], x))
                ~~~~~~~~^~~~~~~~~~

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