Submission #1137780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137780		anmattroi	Aliens (IOI16_aliens)	C++17	100 / 100	176 ms	7916 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
#define maxn 100005
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;
using li = pair<int64_t, int>;

int n, m, k, n1 = 0;
int r[maxn], c[maxn];
ii a[maxn], b[maxn];

li dp[maxn];

//dp[i] = dp[j] - /*fucking worthless*/ + (r[i]-l[j+1])^2
//dp[i] = dp[j] - /*fucking worthless*/ + l[j+1]*l[j+1] + r[i]*r[i] - 2 * r[i] * l[j+1]
//we calc----< min
//-2*l[j+1]-->a decchahhahah

struct line {
    int a; int64_t b;
    line() {}
    line(int _a, int64_t _b) : a(_a), b(_b) {}

    long double intersectX(const line &other) const {
        return (long double) (b-other.b) / (other.a-a);
    }
};

int64_t f(line x, int y) {
    return 1LL * x.a * y + x.b;
}

li solve_lambda(int64_t lambda) {
    deque<pair<line, int> > dq;
    dq.push_back(pair<line, int>{line(-2*a[1].fi, 1LL * a[1].fi * a[1].fi), 0});

    for (int i = 1; i <= n; i++) {
        while (dq.size() >= 2 && f(dq[0].fi, a[i].se+1) >= f(dq[1].fi, a[i].se+1)) dq.pop_front();
        dp[i] = li{lambda + 1LL * (a[i].se+1) * (a[i].se+1) + f(dq.front().fi, a[i].se+1), dq.front().se+1};
        if (i == n) break;

        line cur = line(-2*a[i+1].fi, dp[i].fi - (a[i].se < a[i+1].fi ? 0LL : (1LL * (a[i].se-a[i+1].fi+1)*(a[i].se-a[i+1].fi+1))) + 1LL * a[i+1].fi * a[i+1].fi);
        while (dq.size() >= 2 && dq.back().fi.intersectX(cur) <= dq.back().fi.intersectX(dq[dq.size()-2].fi)) dq.pop_back();
        dq.push_back(pair<line,int>{cur,dp[i].se});
    }
    return dp[n];
}


int n3, m3, k3;
int r3[maxn], c3[maxn];

int64_t solve() {
    n = n3; m = m3; k = k3;
    for (int i = 1; i <= n; i++) {
        r[i] = r3[i];
        c[i] = c3[i];
    }
    for (int i = 1; i <= n; i++) b[i] = {min(r[i], c[i]), max(r[i], c[i])};
    sort(b + 1, b + n + 1, [&](ii x, ii y) {if (x.fi != y.fi) return x.fi < y.fi; return x.se > y.se;});
    int LAST = -100;
    for (int i = 1; i <= n; i++) {
        if (b[i].se <= LAST) continue;
        LAST = b[i].se;
        a[++n1] = b[i];
    }
    n = n1;
    int64_t lo = 0, hi = 100000000000000000LL;
    while (hi - lo > 1LL) {
        int64_t mid = (lo + hi) >> 1LL;
        if (solve_lambda(mid).se >= k) lo = mid;
        else hi = mid;
    }

    return solve_lambda(lo).fi - k * lo;
}


long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    n3 = n; m3 = m; k3 = k;
    for (int i = 0; i < n3; i++) {
        r3[i+1] = r[i];
        c3[i+1] = c[i];
    }
    return solve();
}

/*
5 7 2
0 3
4 4
4 6
4 5
4 6
*/

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