Submission #1227026

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227026		vladilius	Aliens (IOI16_aliens)	C++20	60 / 100	1313 ms	1114112 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{
        ll k, b;
        line(ll ks, ll bs){
            k = ks; b = bs;
        }
        ll operator ()(int x){
            return k * x + b;
        }
        ld inter(line f){
            return 1.0 * (f.b - b) / (k - f.k);
        }
    };
    deque<line> q;
    void add(ll k, ll b){
        line f(k, b);
        while (q.size() >= 2 && q[q.size() - 2].inter(f) <= q[q.size() - 2].inter(q.back())){
            q.pop_back();
        }
        q.pb(f);
    }
    ll get(int x){
        while (q.size() >= 2 && q[0].inter(q[1]) <= x){
            q.pop_front();
        }
        return q[0](x);
    }
};

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;
    vector<vector<ll>> dp(n + 1, vector<ll>(k + 1, inf)); dp[0][0] = 0;
    for (int j = 1; j <= k; j++){
        DS T;
        for (int r = 1; r <= n; r++){
            ll h = f[r - 1].ss - f[r].ff + 1;
            if (h >= 0) h = sq(h);
            else h = 0;
            
            T.add(-2 * (f[r].ff - 1), dp[r - 1][j - 1] + sq(f[r].ff - 1) - h);
            dp[r][j] = sq(f[r].ss) + T.get(f[r].ss);
        }
    }
    
    ll out = inf;
    for (int i = 1; i <= k; i++){
        out = min(out, dp[n][i]);
    }
    return out;
}

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: 0 / 40