Submission #1146202

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146202		Pekiban	Aliens (IOI16_aliens)	C++20	12 / 100	523 ms	752 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];
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 (up[i][u] && X(T[up[i][u]], T[up[0][up[i][u]]]) > x)
            u = up[i][u];
    }
    if (u && X(T[up[0][u]], T[u]) > x) u = up[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;
        int MN[m+1]; fill(MN, MN+m+1, 1e9);
        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 j = i-1;
                    MN[i] = mn[i], up[0][i] = i-1;
                    while (j >= MN[i]) {
                        MN[i] = min(MN[i], MN[j]);
                        j = (MN[j] == 1e9 ? j-1 : MN[j]-1);    
                    }
                    T[i-1] = {(ld)-2*(i-1), dp[i] - i * i + 2 * i * (i-1)}; C[i-1] = C[i];
                    int u = mn[i]-1;
                    int op = f(i, u);
                    dp[i] = T[op].f(i) + i * i + mid, C[i] = C[op]+1;
                    u = MN[i]-1;
                    for (int j = LOG-1; j >= 0; --j) {
                        if (X(T[up[0][up[j][u]]], T[i-1]) <= X(T[up[0][up[j][u]]], T[up[j][u]]))  u = up[j][u];
                    }
                    if (u && X(T[up[0][u]], T[i-1]) <= X(T[up[0][u]], T[u]))    u = up[0][u];
                    up[0][i-1] = u;
                    for (int j = 1; j < LOG; ++j)   up[j][i-1] = up[j-1][up[j-1][i-1]];
                }
            }
            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[up[0][up[j][I]]], T[i]) <= X(T[up[0][up[j][I]]], T[up[j][I]])) I = up[j][I];
            }
            if (I && X(T[up[0][I]], T[i]) <= X(T[up[0][I]], T[I])) I = up[0][I];
            up[0][i] = I;
            for (int j = 1; j < LOG; ++j)   up[j][i] = up[j-1][up[j-1][i]], up[j][i] = up[j-1][up[j-1][i]];
        }
        // cout << mid << ' ' << 
        // if (mid == 1.5625) {
        //     for (int i = 1; i <= m; ++i) {
        //         cout << up[0][i] << ' ' << MN[i] << '\n';
        //     }
        // }
        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