Submission #1291434

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291434		sahtehesap123	Aliens (IOI16_aliens)	C++20	0 / 100	1 ms	344 KiB

aliens

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

constexpr static ll INF = 1e15;

vector<array<int, 2>> get_cells(const vector<int>& r, const vector<int>& c) {
        const int n = r.size();
        vector<array<int, 2>> cells;
        for (int i = 0; i < n; i++) {
                cells.push_back({min(r[i], c[i]), -max(r[i], c[i])});
        }
        sort(cells.begin(), cells.end());
        vector<array<int, 2>> final_cells;
        int lastc = -1;
        for (auto [r, c] : cells) {
                if (-c <= lastc)
                        continue;
                lastc = -c;
                final_cells.push_back({r, -c});
        }
        return final_cells;
}

ll calculate_cost(array<ll, 2> line, ll c) {
        return line[0] + line[1] * c + c * c;
}

bool beating_intercept(const deque<array<ll, 2>>& d, ll y2, ll s2) {
        if (d.size() == 0) return false;
        if (y2 < d[0][0]) return true;
        if (d.size() == 1) return false;
        auto [ y1, s1 ] = d.back();
        auto [ y0, s0 ] = d[d.size()-2];
        assert(y0 <= y1 && y1 <= y2);
        assert(s2 <= s1 && s1 <= s0);
        return (y1 - y2) * (s1 - s0) >= (y0 - y1) * (s2 - s1);
}

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
        assert(n*k <= 1e8);
        vector<array<int, 2>> cells = get_cells(r, c);
        n = cells.size();
        //cout << n << "\n";
        /*
        for (auto [r, c] : cells) {
                cout << r << " " << c << "\n";
        }
        */
        // cout << k << "\n";
        //vector<vector<ll>> dp(n+1, vector<ll>(k+1, INF));
        vector<deque<array<ll, 2>>> dp(k+1); // (Initial point, slope)
        for (int i = 0; i <= k; i++) {
                ll y_intercept = static_cast<ll>(cells[0][0] - 1) * (cells[0][0] - 1);
                ll slope       = - 2 * (cells[0][0] - 1);
                dp[i].push_back({y_intercept, slope});
                //cout << i << " " << 0 << ": " << y_intercept << " + " << slope << "x\n";
        }
        for (int j = 1; j <= k; j++) {
                for (int i = 1; i <= n; i++) {
                        auto [r, c] = cells[i-1];
                        while (dp[j-1].size() > 1 && calculate_cost(dp[j-1][0], c) > calculate_cost(dp[j-1][1], c)) dp[j-1].pop_front();
                        ll cost = calculate_cost(dp[j-1][0], c);
                        if (i < n) {
                                ll y_intercept = cost + static_cast<ll>(cells[i][0] - 1) * (cells[i][0] - 1) - max<ll>(0, c - cells[i][0] + 1) * max<ll>(0, c - cells[i][0] + 1);
                                ll slope = - 2 * (cells[i][0] - 1);
                                while (beating_intercept(dp[j], y_intercept, slope)) dp[j].pop_back();
                                dp[j].push_back({y_intercept, slope});
                                //cout << j << " " << i << ": " << y_intercept << " + " << slope << "x\n";
                        }
                        if (i == n && j == k) {
                                return cost;
                        }
                }
        }
        assert(false);
}

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