Submission #1137777

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137777		anmattroi	Aliens (IOI16_aliens)	C++17	Compilation error	0 ms	0 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];
}

int64_t solve() {
    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;
}

int64_t take_photos(int N, int M, int K, vector<int> R, vector<int> C) {
    n = N; m = M; k = K;
    for (int i = 0; i < n; i++) {
        r[i+1] = R[i];
        c[i+1] = C[i];
    }
    return solve();
}

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

Compilation message (stderr)

aliens.cpp:71:9: error: ambiguating new declaration of 'int64_t take_photos(int, int, int, std::vector<int>, std::vector<int>)'
   71 | int64_t take_photos(int N, int M, int K, vector<int> R, vector<int> C) {
      |         ^~~~~~~~~~~
In file included from aliens.cpp:1:
aliens.h:5:11: note: old declaration 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)'
    5 | long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c);
      |           ^~~~~~~~~~~
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
      |         ^~~~