Submission #1197747

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197747		vjudge2	Aliens (IOI16_aliens)	C++20	100 / 100	187 ms	8064 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;

using i32 = int32_t;
#define int long long

struct Line {
    int m, c;
    int eval(int x) { return m * x + c; }
    long double intersectX(Line l) { return (long double) (c - l.c) / (l.m - m); }
};

int take_photos(i32 n, i32 m, i32 K, std::vector<i32> r, std::vector<i32> c) {
    vector<pair<int, int>> p;
    for (int i = 0; i < n; i++) if (r[i] > c[i]) swap(r[i], c[i]);
    for (int i = 0; i < n; i++) p.push_back({r[i], c[i]});
    sort(p.begin(), p.end(), [] (auto x, auto y) {
        if (x.first == y.first) return x.second > y.second;
        return x.first < y.first;
    });
    int rmx = -1;
    vector<int> L, R;
    for (int i = 0; i < n; i++) {
        if (rmx < p[i].second) {
            L.push_back(p[i].first);
            R.push_back(p[i].second);
            rmx = p[i].second;
        } 
    }
    // deque<Line> q[K+1];
    int N = L.size();
    const int inf = 1e18;
    auto solve_lambda = [&] (int c) {
        // cout << c << '\n';
        vector<pair<int, int>> dp(N);
        deque<pair<Line, int>> q;
        q.push_back({{-2 * (L[0] - 1), (L[0] - 1) * (L[0] - 1) + c}, 0}); // (r[i] - l[0] + 1) * (r[i] - l[0] + 1) = r[i]^2 - 2 * r[i] * (l[0] - 1) + (l[0] - 1) * (l[0] - 1);
        for (int i = 0; i < N; i++) {
            int pos = R[i];
            while (q.size() >= 2 && q[0].first.eval(pos) > q[1].first.eval(pos)) q.pop_front();
            if (!q.empty()) {
                dp[i].first = q[0].first.eval(pos) + R[i] * R[i];
                dp[i].second = q[0].second + 1;
            }
            if (i < N - 1) {
                Line cur;
                if (R[i] < L[i + 1]) cur = {-2 * (L[i+1] - 1), (L[i+1] - 1) * (L[i+1] - 1) + dp[i].first + c};
                else cur = {-2 * (L[i+1] - 1), -R[i] * R[i] + 2 * (R[i]) * (L[i+1] - 1) + dp[i].first + c};
                for (int k = q.size(); k >= 2 && q[k-2].first.intersectX(q[k-1].first) >= q[k-1].first.intersectX(cur); k--) q.pop_back();
                q.push_back({cur, dp[i].second});
            }
        }
        return dp[N - 1];
    };
    int lo = 0, hi = inf, ans = inf;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        pair<int, int> res = solve_lambda(mid);
        if (res.second <= K) {
            hi = mid - 1;
            ans = mid;
        }
        else lo = mid + 1;
    }
    // cout << lo << " " << res.first << " " << res.second << '\n';
    // for (int i = 0; i <= 5; i++) {
    //     pair<int, int> res = solve_lambda(i);
    //     cout << res.first << " " << res.second << '\n';
    // }
    pair<int, int> res = solve_lambda(ans);
    return res.first - ans * K;
    // cout << dp[K][N-1] << '\n';
    // m = -2*(l[j+1] - 1)
    // c = asdfasdfasdfasdf
    // our query positions are increasing
    // we want to find min

    // m decreasing 
    // query positions increasing 
    // find minimum 
    // dp[i][k] = min(dp[j][k-1], (r[i] - l[j+1] + 1) * (r[i] - l[j+1] + 1) - (r[j] - l[j+1] + 1) * (r[j] - l[j+1] + 1));
    // r[i]^2 - 2 * r[i] * (l[j+1] - 1) - r[j]^2 + 2 * (r[j]) * (l[j+1] - 1) // last part omit if r[j] < l[j+1]
}

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