Submission #1227600

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227600		vladilius	Aliens (IOI16_aliens)	C++20	100 / 100	275 ms	9184 KiB

aliens

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
const ll inf = 1e18;

struct DS{
    struct line{
        ld k, b;
        int i;
        line(ld ks, ld bs, int is){
            k = ks; b = bs; i = is;
        }
        ld operator ()(int x){
            return k * x + b;
        }
        ld inter(line f){
            return (f.b - b) / (k - f.k);
        }
    };
    deque<line> q;
    void add(ld k, ld b, int i){
        line f(k, b, i);
        while (q.size() >= 2 && q[q.size() - 2].inter(f) <= q[q.size() - 2].inter(q.back())){
            q.pop_back();
        }
        q.pb(f);
    }
    pair<ld, int> get(int x){
        while (q.size() >= 2 && q[0].inter(q[1]) <= x){
            q.pop_front();
        }
        return {q[0](x), q[0].i};
    }
    void clear(){
        q.clear();
    }
};

ll take_photos(int n, int m, int k, vector<int> r, vector<int> c){
    vector<pii> all;
    for (int i = 0; i < n; i++){
        if (r[i] > c[i]) swap(r[i], c[i]);
        all.pb({r[i], c[i]});
    }
    
    auto cmp = [&](pii x, pii y){
        if (x.ff != y.ff) return x.ff < y.ff;
        return x.ss > y.ss;
    };
    
    sort(all.begin(), all.end(), cmp);
    
    auto sq = [&](ll x){
        return x * x;
    };
    
    vector<pii> f = {{-1, -1}};
    int X = -1, Y = -1;
    for (auto [x, y]: all){
        if (X < x && Y < y){
            f.pb({x, y});
            X = x; Y = y;
        }
    }

    n = (int) f.size() - 1; k = min(k, n);
    
    vector<pair<ld, int>> dp(n + 1);
    DS T;
    auto F = [&](ld M){
        T.clear();
        for (int i = 1; i <= n; i++){
            ll h = f[i - 1].ss - f[i].ff + 1;
            if (h > 0) h = sq(h);
            else h = 0;
            
            T.add(-2 * (f[i].ff - 1), dp[i - 1].ff + sq(f[i].ff - 1) - h, i);

            auto [v, j] = T.get(f[i].ss);
            dp[i] = {sq(f[i].ss) + v + M, dp[j - 1].ss + 1};
        }
        return dp[n];
    };

    ld L = 0, R = 1e12;
    while ((R - L) >= 1e-4){
        ld M = (L + R) / 2;
        if (F(M).ss < k){
            R = M;
        }
        else {
            L = M;
        }
    }
    
    auto [v, x] = F(L);
    return (ll) round(v - k * L);
}

Compilation message (stderr)

aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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