Submission #1197706

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197706		vjudge2	Aliens (IOI16_aliens)	C++20	12 / 100	9 ms	2884 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;
        } 
    }
    // for (int i = 0; i < L.size(); i++) cout << "hi " << L[i] << " " << R[i] << '\n';
    deque<Line> q[K+1];
    int N = L.size();
    const int inf = 1e18;
    vector<vector<int>> dp(K+1, vector<int> (N, inf));
    q[0].push_back({-2 * (L[0] - 1), (L[0] - 1) * (L[0] - 1)}); // (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++) {
        for (int j = K - 1; j >= 0; j--) {
            int pos = R[i];
            while (q[j].size() >= 2 && q[j][0].eval(pos) > q[j][1].eval(pos)) q[j].pop_front();
            if (!q[j].empty()) dp[j+1][i] = q[j][0].eval(pos) + R[i] * R[i];
            if (i < N - 1) {
                Line cur;
                if (i == 0 || R[i] < L[i + 1]) cur = {-2 * (L[i+1] - 1), (L[i+1] - 1) * (L[i+1] - 1) + dp[j+1][i]};
                else cur = {-2 * (L[i+1] - 1), -R[i] * R[i] + 2 * (R[i]) * (L[i+1] - 1) + dp[j+1][i]};
                for (int k = q[j+1].size(); k >= 2 && q[j+1][k-2].intersectX(q[j+1][k-1]) >= q[j+1][k-1].intersectX(cur); k--) q[j+1].pop_back();
                q[j+1].push_back(cur);
            }
        }
    }
    int ans = inf;
    for (int i = 0; i <= K; i++) ans = min(ans, dp[i][N - 1]);
    // for (int j = 1; j <= K; j++) {
    //     for (int i = 0; i < N; i++) cout << dp[j][i] << " ";
    //     cout << '\n';
    // }
    return ans;
    // 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: 0 / 4
• Subtask 2: 12 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40