Submission #1146167

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146167		Pekiban	Aliens (IOI16_aliens)	C++20	12 / 100	522 ms	980 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

const int M = 1e6 + 5, LOG = 20;
int up[LOG][M], up2[LOG][M];
deque<int> dq;
ld dp[M], C[M];
struct line {
    ld k, c;
    ld f(ld x) {
        return k * x + c;
    };
} T[M];
ld X(line &A, line &B) {
    return (ld)(A.c - B.c) / (B.k - A.k);
}
int f(int x, int u) {
    for (int i = LOG-1; i >= 0; --i) {
        if (up2[i][u] && X(T[up2[i][u]], T[up2[0][up2[i][u]]]) > x)
            u = up2[i][u];
    }
    if (u && X(T[up2[0][u]], T[u]) > x) u = up2[0][u];
    return u;
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    int mn[m+1];
    fill(mn, mn+m+1, 1e9);
    for (int i = 0; i < n; ++i) r[i]++, c[i]++;
    for (int i = 0; i < n; ++i) mn[max(r[i], c[i])] = min({mn[max(r[i], c[i])], r[i], c[i]});
    ld L = 0, R = m * (1ll) * m, ans = 1e18;
    for (int _ = 0; _ < 200; ++_) {
        ld mid = (L + R)/2;
        T[0] = {0, 0}, dq = {0}, C[0] = 0;
        for (ll i = 1; i <= m; ++i) {
            if (mn[i] != 1e9) {
                if (mn[i] == i) {
                    int op = f(i, i-1);
                    dp[i] = T[op].f(i) + i * i + mid, up[0][i] = i-1, C[i] = C[op]+1;;
                }
                else {
                    int u = i-1;
                    for (int j = LOG-1; j >= 0; --j) {
                        if (up[j][u] >= mn[i])  u = up[j][u];
                    }
                    int op = f(i, up[0][u]);
                    dp[i] = T[op].f(i) + i * i + mid, up[0][i] = u, C[i] = C[op]+1;
                    T[u] = {(ld)-2*u, dp[i] - i * i + 2 * i * u}; C[u] = C[i];
                    int U = up2[0][u];
                    for (int j = LOG-1; j >= 0; --j) {
                        if (X(T[up2[0][up2[j][U]]], T[u]) <= X(T[up2[0][up2[j][U]]], T[up2[j][U]])) U = up2[j][U];
                    }
                    up2[0][u] = U;
                    for (int j = 1; j < LOG; ++j)   up2[j][u] = up2[j-1][up2[j-1][u]];
                }
            }
            else
                dp[i] = dp[i-1], C[i] = C[i-1], up[0][i] = i-1;
            T[i] = {(ld)-2*i, dp[i] - i * i + 2 * i * i};
            int I = up[0][i];
            for (int j = LOG-1; j >= 0; --j) {
                if (X(T[up2[0][up2[j][I]]], T[i]) <= X(T[up2[0][up2[j][I]]], T[up2[j][I]])) I = up2[j][I];
            }
            if (I && X(T[up2[0][I]], T[i]) <= X(T[up2[0][I]], T[I])) I = up2[0][I];
            up2[0][i] = I;
            for (int j = 1; j < LOG; ++j)   up2[j][i] = up2[j-1][up2[j-1][i]], up[j][i] = up[j-1][up[j-1][i]];
        }
        if (C[m] <= k)
            R = mid, ans = dp[m] - k * mid;
        else
            L = mid;
    }
    return roundl(ans);
}

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: 0 / 4
• Subtask 2: 12 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40