Кодерун планирует идеальный летний день в парке ...

Question

Кодерун планирует идеальный летний день в парке отдыха. Он хочет успеть побывать в самых интересных местах, не выйти за бюджет и не потратить на дорогу слишком много времени.

Организаторы подготовили API-сервер с данными о местах отдыха. Ваша программа должна обращаться к этому серверу, получать нужные данные и строить оптимальный маршрут на один день.

Маршрут:

text
начинается в стартовой точке start;
состоит из последовательности различных мест;
учитывает время в пути между соседними точками;
укладывается в ограничение по времени и бюджету.

Для каждого места известны:

text
id — идентификатор;
type — тип места;
visit_time_minutes — длительность посещения;
cost — стоимость;
rating — рейтинг;
weather_sensitive — зависит ли полезность посещения от погоды;
open_from, open_to — часы работы.

Дополнительно сервер знает:

text
стартовую точку;
прогноз погоды для каждого места;
время в пути между любыми двумя точками;
коэффициенты функции оценки.

Что нужно максимизировать

Для корректного маршрута score вычисляется по формуле:

rating_sum * rating_weight + diversity * diversity_weight - travel_sum * travel_penalty - bad_weather_count * bad_weather_penalty

где:

text
rating_sum — сумма рейтингов посещенных мест;
diversity — число различных типов мест в маршруте;
travel_sum — суммарное время в пути;
bad_weather_count — число посещенных weather-sensitive мест с плохой погодой (rainy или windy).

Требуется вывести маршрут с максимальным score. Если существует несколько оптимальных маршрутов, допускается вывести любой из них.
Формат ввода

На стандартный ввод вашей программы подаются:

text
в первой строке base_url локального API-сервера;
во второй строке day_id — идентификатор текущего сценария.

Ограничения:

text
base_url — корректный URL вида http://127.0.0.1:<port>;
day_id — целое число;
в тестах количество мест n n удовлетворяет 8 <= n <= 16;
240 <= time_limit_minutes <= 600;
1500 <= budget <= 12000;
для каждого места: 20 <= visit_time_minutes <= 180, 0 <= cost <= 2500, 1.0 <= rating <= 10.0.

Формат вывода

Если маршрут пустой, выведите:

0

Иначе выведите:

text
в первой строке число k — количество мест в маршруте;
во второй строке k различных идентификаторов мест в порядке посещения.

Пример
Данные потока ввода:

http://127.0.0.1:8080
42

Данные сервера:
Ответ GET /day/42:

{
"day_id": "42",
"start_point": {
"id": "start",
"x": 0,
"y": 0
},
"time_limit_minutes": 720,
"budget": 5000,
"score_weights": {
"rating": 100,
"diversity": 50,
"travel_penalty": 1,
"bad_weather_penalty": 80
}
}

Ответ GET /places?day_id=42:

{
"day_id": "42",
"places": [
{
"id": 101,
"type": "beach"
},
{
"id": 102,
"type": "cafe"
},
{
"id": 103,
"type": "viewpoint"
}
]
}

Ответ POST /places/batch с телом

{
"ids": [101, 102, 103]
}

{
"places": [
{
"id": 101,
"type": "beach",
"visit_time_minutes": 90,
"cost": 700,
"rating": 8.7,
"weather_sensitive": true,
"open_from": "08:00",
"open_to": "20:00"
},
{
"id": 102,
"type": "cafe",
"visit_time_minutes": 40,
"cost": 1200,
"rating": 9.1,
"weather_sensitive": false,
"open_from": "10:00",
"open_to": "23:00"
},
{
"id": 103,
"type": "viewpoint",
"visit_time_minutes": 30,
"cost": 0,
"rating": 8.4,
"weather_sensitive": true,
"open_from": "06:00",
"open_to": "21:00"
}
]
}

Ответ POST /travel-time/matrix с телом

{
"ids": ["start", 101, 102, 103]
}

{
"ids": ["start", "101", "102", "103"],
"matrix": [
[0, 25, 20, 45],
[25, 0, 15, 30],
[20, 15, 0, 20],
[45, 30, 20, 0]
]
}

Ответы GET /weather?day_id=42&place_id={id} для этих мест:

{
"day_id": "42",
"place_id": "101",
"weather": "sunny"
}

{
"day_id": "42",
"place_id": "102",
"weather": "cloudy"
}

{
"day_id": "42",
"place_id": "103",
"weather": "windy"
}

Вывод

3
5 2 7

Примечание

text
Сервер доступен только во время текущего запуска программы.
Проверяющая система не требует буквального совпадения с эталонным маршрутом: принимается любой маршрут с оптимальным score.
Время ожидания открытия места в текущих тестах не требуется: все места открыты почти весь день, но поля open_from и open_to всё равно присутствуют в API и должны учитываться как часть формата.

Разбор примера

Документация API

Ограничения

Ограничение времени
5 с
Ограничение памяти
512 МБ

Примеры
Пример 1
Ввод

{
"public": {
"day_id": 42
},
"private": {
"server": {
"start_point": {
"id": "start",
"x": 0,
"y": 0
},
"time_limit_minutes": 720,
"budget": 5000,
"score_weights": {
"rating": 100,
"diversity": 50,
"travel_penalty": 1,
"bad_weather_penalty": 80
},
"places": [
{
"id": 101,
"type": "beach",
"x": 10,
"y": 20,
"visit_time_minutes": 90,
"cost": 700,
"rating": 8.7,
"weather_sensitive": true,
"open_from": "08:00",
"open_to": "20:00"
},
{
"id": 102,
"type": "cafe",
"x": 13,
"y": 18,
"visit_time_minutes": 40,
"cost": 1200,
"rating": 9.1,
"weather_sensitive": false,
"open_from": "10:00",
"open_to": "23:00"
},
{
"id": 103,
"type": "viewpoint",
"x": 22,
"y": 30,
"visit_time_minutes": 30,
"cost": 0,
"rating": 8.4,
"weather_sensitive": true,
"open_from": "06:00",
"open_to": "21:00"
}
],
"weather": {
"101": "sunny",
"102": "cloudy",
"103": "windy"
},
"travel_time_minutes": {
"start:101": 25,
"start:102": 20,
"start:103": 45,
"101:102": 15,
"101:103": 30,
"102:101": 15,
"102:103": 20,
"103:101": 30,
"103:102": 20
}
}
}
}

Вывод

3
101 102 103

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <cstdint>

#include <curl/curl.h>
#include "json.hpp"

using json = nlohmann::json;

// ==================== HTTP через libcurl ====================
static std::string g_base;

static size_t writeCb(char *ptr, size_t size, size_t nmemb, void userdata) {
((std::string)userdata)->append(ptr, size * nmemb);
return size * nmemb;
}

static json httpGetJson(const std::string &path) {
std::string resp;
CURL *curl = curl_easy_init();
curl_easy_setopt(curl, CURLOPT_URL, (g_base + path).c_str());
curl_easy_setopt(curl, CURLOPT_WRITEFUNCTION, writeCb);
curl_easy_setopt(curl, CURLOPT_WRITEDATA, &resp);
curl_easy_perform(curl);
curl_easy_cleanup(curl);
return json::parse(resp, nullptr, false);
}

static json httpPostJson(const std::string &path, const json &body) {
std::string resp;
std::string payload = body.dump();
CURL *curl = curl_easy_init();
struct curl_slist *hdrs = nullptr;
hdrs = curl_slist_append(hdrs, "Content-Type: application/json");
curl_easy_setopt(curl, CURLOPT_URL, (g_base + path).c_str());
curl_easy_setopt(curl, CURLOPT_HTTPHEADER, hdrs);
curl_easy_setopt(curl, CURLOPT_POSTFIELDS, payload.c_str());
curl_easy_setopt(curl, CURLOPT_POSTFIELDSIZE, (long)payload.size());
curl_easy_setopt(curl, CURLOPT_WRITEFUNCTION, writeCb);
curl_easy_setopt(curl, CURLOPT_WRITEDATA, &resp);
curl_easy_perform(curl);
curl_slist_free_all(hdrs);
curl_easy_cleanup(curl);
return json::parse(resp, nullptr, false);
}

// id может быть числом или строкой — нормализуем в строку
static std::string idToStr(const json &v) {
if (v.is_string()) return v.getstd::string();
return std::to_string(v.get<long long>());
}

int main() {
std::string base_url, day_id;
std::getline(std::cin, base_url);
std::getline(std::cin, day_id);
// подчистим возможные \r и пробелы (Windows-переводы строк в тестах)
while (!base_url.empty() && (base_url.back() == '\r' || base_url.back() == ' ')) base_url.pop_back();
while (!day_id.empty() && (day_id.back() == '\r' || day_id.back() == ' ')) day_id.pop_back();
g_base = base_url;

text
curl_global_init(CURL_GLOBAL_DEFAULT);

// ---- 1. Параметры дня ----
json day = httpGetJson("/day/" + day_id);
double timeLimit = day["time_limit_minutes"].get<double>();
double budget    = day["budget"].get<double>();
double wRating = day["score_weights"]["rating"].get<double>();
double wDiv    = day["score_weights"]["diversity"].get<double>();
double wTravel = day["score_weights"]["travel_penalty"].get<double>();
double wBad    = day["score_weights"]["bad_weather_penalty"].get<double>();
json startIdRaw = day["start_point"]["id"];
std::string startId = idToStr(startIdRaw);

// ---- 2. Список мест ----
json plist = httpGetJson("/places?day_id=" + day_id);
std::vector<json> rawIds;                  // сохраняем исходный JSON-тип id
for (auto &pl : plist["places"]) rawIds.push_back(pl["id"]);
int n = (int)rawIds.size();
if (n == 0) { std::cout << 0 << '\n'; return 0; }

// ---- 3. Детали мест ----
json batchBody;
batchBody["ids"] = json::array();
for (auto &r : rawIds) batchBody["ids"].push_back(r);
json batch = httpPostJson("/places/batch", batchBody);

std::vector<std::string> ids(n);
std::vector<double> visitT(n), cost(n), rating(n);
std::vector<bool> wsens(n);
std::vector<int> typeId(n);
std::map<std::string, int> typeMap, idIndex;

{
    int i = 0;
    for (auto &pl : batch["places"]) {
        ids[i] = idToStr(pl["id"]);
        idIndex[ids[i]] = i;
        visitT[i] = pl["visit_time_minutes"].get<double>();
        cost[i]   = pl["cost"].get<double>();
        rating[i] = pl["rating"].get<double>();
        wsens[i]  = pl["weather_sensitive"].get<bool>();
        std::string t = pl["type"].get<std::string>();
        if (!typeMap.count(t)) typeMap[t] = (int)typeMap.size();
        typeId[i] = typeMap[t];
        ++i;
    }
    n = i;
}

// ---- 4. Матрица времени в пути: start + все места ----
json mBody;
mBody["ids"] = json::array();
mBody["ids"].push_back(startIdRaw);
for (auto &r : rawIds) mBody["ids"].push_back(r);
json mresp = httpPostJson("/travel-time/matrix", mBody);

// строки матрицы сопоставляем по echoed ids: start -> индекс n, места -> 0..n-1
std::vector<int> rowOf(n + 1, -1);
{
    auto &echo = mresp["ids"];
    for (int r = 0; r < (int)echo.size(); ++r) {
        std::string eid = idToStr(echo[r]);
        if (eid == startId) rowOf[n] = r;
        else if (idIndex.count(eid)) rowOf[idIndex[eid]] = r;
    }
}
std::vector<std::vector<double>> tt(n + 1, std::vector<double>(n + 1, 0));
auto &mat = mresp["matrix"];
for (int i = 0; i <= n; ++i)
    for (int j = 0; j <= n; ++j)
        tt[i][j] = mat[rowOf[i]][rowOf[j]].get<double>();

// ---- 5. Погода по каждому месту ----
std::vector<bool> badW(n, false);
for (int i = 0; i < n; ++i) {
    json wr = httpGetJson("/weather?day_id=" + day_id + "&place_id=" + ids[i]);
    std::string ws = wr["weather"].get<std::string>();
    badW[i] = wsens[i] && (ws == "rainy" || ws == "windy");
}

// ==================== Битмасковая ДП ====================
// dp[mask][last] — минимальное суммарное время в пути, посетив mask и стоя в last
int full = 1 << n;
const double INF = 1e18;
std::vector<double> dp((size_t)full * n, INF);
std::vector<int8_t> par((size_t)full * n, -1);

// агрегаты по маске через младший бит
std::vector<double> mVisit(full, 0), mCost(full, 0), mRate(full, 0);
std::vector<int> mBad(full, 0), mTypes(full, 0);
for (int mask = 1; mask < full; ++mask) {
    int i = __builtin_ctz(mask);
    int rest = mask & (mask - 1);
    mVisit[mask] = mVisit[rest] + visitT[i];
    mCost[mask]  = mCost[rest] + cost[i];
    mRate[mask]  = mRate[rest] + rating[i];
    mBad[mask]   = mBad[rest] + (badW[i] ? 1 : 0);
    mTypes[mask] = mTypes[rest] | (1 << typeId[i]);
}

for (int i = 0; i < n; ++i)
    dp[(size_t)(1 << i) * n + i] = tt[n][i];

double bestScore = 0;   // пустой маршрут = 0
int bestMask = 0, bestLast = -1;

for (int mask = 1; mask < full; ++mask) {
    if (mCost[mask] > budget) continue;
    double vsum = mVisit[mask];
    double baseScore = mRate[mask] * wRating
                     + __builtin_popcount(mTypes[mask]) * wDiv
                     - mBad[mask] * wBad;
    for (int last = 0; last < n; ++last) {
        if (!(mask >> last & 1)) continue;
        double d = dp[(size_t)mask * n + last];
        if (d >= INF || d + vsum > timeLimit) continue;

        double sc = baseScore - d * wTravel;
        if (sc > bestScore) { bestScore = sc; bestMask = mask; bestLast = last; }

        for (int j = 0; j < n; ++j) {
            if (mask >> j & 1) continue;
            double nd = d + tt[last][j];
            size_t idx = (size_t)(mask | 1 << j) * n + j;
            if (nd < dp[idx]) { dp[idx] = nd; par[idx] = (int8_t)last; }
        }
    }
}

// ---- Восстановление и вывод ----
if (bestLast < 0) { std::cout << 0 << '\n'; return 0; }

std::vector<int> path;
int mask = bestMask, last = bestLast;
while (last >= 0) {
    path.push_back(last);
    int pl = par[(size_t)mask * n + last];
    mask ^= 1 << last;
    last = pl;
}

std::cout << path.size() << '\n';
for (size_t i = path.size(); i-- > 0; )
    std::cout << ids[path[i]] << (i == 0 ? '\n' : ' ');
return 0;

}

1

Тест пройден
575 мс
808 кБ

Бенчмарк учитывается в зачёте и проверяется несколько раз на стабильность. Результатом считается среднее время
ID
Вердикт
Время
Память

2

Тест пройден
577 мс
672 кБ

3

Тест пройден
577 мс
676 кБ

4

Тест пройден
577 мс
808 кБ

5

Тест пройден
578 мс
936 кБ

6

Тест пройден
577 мс
808 кБ

7

Тест пройден
576 мс
932 кБ

8

Тест пройден
580 мс
808 кБ

9

Тест пройден
581 мс
804 кБ

10

Тест пройден
582 мс
1,07 МБ

11

Тест пройден
583 мс
5,62 МБ

12

Тест пройден
583 мс
6,59 МБ

Optimize the code

Answer 1

Главный bottleneck — не DP, а HTTP: при n = 16 исходная версия выполняет 20 последовательных запросов, каждый раз создавая новый CURL-handle. Ниже запросы объединены в две параллельные волны через curl_multi, а DP переведена на целочисленное время и обход установленных битов.

cpp
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <limits>
#include <stdexcept>
#include <string>
#include <unordered_map>
#include <vector>

#include <curl/curl.h>
#include "json.hpp"

using json = nlohmann::json;

// ============================================================
// HTTP
// ============================================================

struct HttpRequest {
    std::string path;
    std::string body;
    bool post = false;
};

static std::string g_base;

static size_t writeCallback(
    char* data,
    size_t size,
    size_t count,
    void* userdata
) {
    const size_t bytes = size * count;
    static_cast<std::string*>(userdata)->append(data, bytes);
    return bytes;
}

static std::vector<json> performRequests(
    const std::vector<HttpRequest>& requests
) {
    const size_t requestCount = requests.size();

    if (requestCount == 0) {
        return {};
    }

    CURLM* multi = curl_multi_init();
    if (!multi) {
        throw std::runtime_error("curl_multi_init failed");
    }

    std::vector<CURL*> handles(requestCount, nullptr);
    std::vector<curl_slist*> headers(requestCount, nullptr);
    std::vector<std::string> urls(requestCount);
    std::vector<std::string> responses(requestCount);
    std::vector<CURLcode> curlCodes(
        requestCount,
        CURLE_FAILED_INIT
    );

    std::unordered_map<CURL*, size_t> handleIndex;
    handleIndex.reserve(requestCount * 2);

    for (size_t i = 0; i < requestCount; ++i) {
        urls[i] = g_base + requests[i].path;

        CURL* curl = curl_easy_init();
        if (!curl) {
            throw std::runtime_error("curl_easy_init failed");
        }

        handles[i] = curl;
        handleIndex.emplace(curl, i);

        curl_easy_setopt(curl, CURLOPT_URL, urls[i].c_str());
        curl_easy_setopt(curl, CURLOPT_WRITEFUNCTION, writeCallback);
        curl_easy_setopt(curl, CURLOPT_WRITEDATA, &responses[i]);

        curl_easy_setopt(curl, CURLOPT_NOSIGNAL, 1L);
        curl_easy_setopt(curl, CURLOPT_TCP_NODELAY, 1L);

        curl_easy_setopt(curl, CURLOPT_CONNECTTIMEOUT_MS, 1500L);
        curl_easy_setopt(curl, CURLOPT_TIMEOUT_MS, 4500L);

        if (requests[i].post) {
            headers[i] = curl_slist_append(
                headers[i],
                "Content-Type: application/json"
            );

            curl_easy_setopt(curl, CURLOPT_HTTPHEADER, headers[i]);
            curl_easy_setopt(curl, CURLOPT_POST, 1L);
            curl_easy_setopt(
                curl,
                CURLOPT_POSTFIELDS,
                requests[i].body.data()
            );
            curl_easy_setopt(
                curl,
                CURLOPT_POSTFIELDSIZE,
                static_cast<long>(requests[i].body.size())
            );
        }

        if (curl_multi_add_handle(multi, curl) != CURLM_OK) {
            throw std::runtime_error("curl_multi_add_handle failed");
        }
    }

    int running = 0;

    CURLMcode multiCode;
    do {
        multiCode = curl_multi_perform(multi, &running);
    } while (multiCode == CURLM_CALL_MULTI_PERFORM);

    while (multiCode == CURLM_OK && running > 0) {
        int fileDescriptors = 0;

        multiCode = curl_multi_wait(
            multi,
            nullptr,
            0,
            1000,
            &fileDescriptors
        );

        if (multiCode != CURLM_OK) {
            break;
        }

        do {
            multiCode = curl_multi_perform(multi, &running);
        } while (multiCode == CURLM_CALL_MULTI_PERFORM);
    }

    int messagesLeft = 0;

    while (CURLMsg* message =
               curl_multi_info_read(multi, &messagesLeft)) {
        if (message->msg != CURLMSG_DONE) {
            continue;
        }

        const auto it = handleIndex.find(message->easy_handle);
        if (it != handleIndex.end()) {
            curlCodes[it->second] = message->data.result;
        }
    }

    bool requestFailed = multiCode != CURLM_OK;

    for (size_t i = 0; i < requestCount; ++i) {
        long httpCode = 0;
        curl_easy_getinfo(
            handles[i],
            CURLINFO_RESPONSE_CODE,
            &httpCode
        );

        if (curlCodes[i] != CURLE_OK ||
            httpCode < 200 ||
            httpCode >= 300) {
            requestFailed = true;
        }

        curl_multi_remove_handle(multi, handles[i]);
        curl_easy_cleanup(handles[i]);

        if (headers[i]) {
            curl_slist_free_all(headers[i]);
        }
    }

    curl_multi_cleanup(multi);

    if (requestFailed) {
        throw std::runtime_error("HTTP request failed");
    }

    std::vector<json> result(requestCount);

    for (size_t i = 0; i < requestCount; ++i) {
        result[i] = json::parse(responses[i]);
    }

    return result;
}

static std::string idToString(const json& value) {
    if (value.is_string()) {
        return value.get<std::string>();
    }

    if (value.is_number_unsigned()) {
        return std::to_string(
            value.get<unsigned long long>()
        );
    }

    if (value.is_number_integer()) {
        return std::to_string(
            value.get<long long>()
        );
    }

    return value.dump();
}

// ============================================================
// Main
// ============================================================

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::string dayId;

    std::getline(std::cin, g_base);
    std::getline(std::cin, dayId);

    while (!g_base.empty() &&
           (g_base.back() == '\r' || g_base.back() == ' ')) {
        g_base.pop_back();
    }

    while (!dayId.empty() &&
           (dayId.back() == '\r' || dayId.back() == ' ')) {
        dayId.pop_back();
    }

    curl_global_init(CURL_GLOBAL_DEFAULT);

    try {
        // Первая пара запросов не зависит друг от друга.
        const std::vector<json> firstResponses =
            performRequests({
                {
                    "/day/" + dayId,
                    "",
                    false
                },
                {
                    "/places?day_id=" + dayId,
                    "",
                    false
                }
            });

        const json& day = firstResponses[0];
        const json& placeList = firstResponses[1];

        const int timeLimit =
            day.at("time_limit_minutes").get<int>();

        const int budget =
            day.at("budget").get<int>();

        const json& weights = day.at("score_weights");

        const double ratingWeight =
            weights.at("rating").get<double>();

        const double diversityWeight =
            weights.at("diversity").get<double>();

        const double travelPenalty =
            weights.at("travel_penalty").get<double>();

        const double badWeatherPenalty =
            weights.at("bad_weather_penalty").get<double>();

        const json startIdRaw =
            day.at("start_point").at("id");

        const std::string startId =
            idToString(startIdRaw);

        std::vector<json> rawIds;
        rawIds.reserve(placeList.at("places").size());

        for (const json& place : placeList.at("places")) {
            rawIds.push_back(place.at("id"));
        }

        const int n = static_cast<int>(rawIds.size());

        if (n == 0) {
            std::cout << 0 << '\n';
            curl_global_cleanup();
            return 0;
        }

        json batchBody;
        batchBody["ids"] = rawIds;

        json matrixBody;
        matrixBody["ids"] = json::array();
        matrixBody["ids"].push_back(startIdRaw);

        for (const json& id : rawIds) {
            matrixBody["ids"].push_back(id);
        }

        /*
         * Вторая волна:
         *
         * 1. детали всех мест;
         * 2. матрица времени;
         * 3. погода для каждого места.
         *
         * Все эти запросы уже независимы.
         */
        std::vector<HttpRequest> secondRequests;
        secondRequests.reserve(static_cast<size_t>(n) + 2);

        secondRequests.push_back({
            "/places/batch",
            batchBody.dump(),
            true
        });

        secondRequests.push_back({
            "/travel-time/matrix",
            matrixBody.dump(),
            true
        });

        for (const json& id : rawIds) {
            secondRequests.push_back({
                "/weather?day_id=" + dayId +
                    "&place_id=" + idToString(id),
                "",
                false
            });
        }

        const std::vector<json> secondResponses =
            performRequests(secondRequests);

        const json& batch = secondResponses[0];
        const json& matrixResponse = secondResponses[1];

        // За основной порядок берём порядок /places.
        std::vector<std::string> ids(n);

        std::unordered_map<std::string, int> idIndex;
        idIndex.reserve(static_cast<size_t>(n) * 2);

        for (int i = 0; i < n; ++i) {
            ids[i] = idToString(rawIds[i]);
            idIndex.emplace(ids[i], i);
        }

        std::vector<int> visitTime(n);
        std::vector<int> costs(n);
        std::vector<int> typeId(n);

        std::vector<double> ratings(n);

        std::vector<uint8_t> weatherSensitive(n, 0);
        std::vector<uint8_t> badWeather(n, 0);

        std::unordered_map<std::string, int> typeIndex;
        typeIndex.reserve(static_cast<size_t>(n) * 2);

        // Сервер не обязан возвращать batch в порядке запроса.
        for (const json& place : batch.at("places")) {
            const int index =
                idIndex.at(idToString(place.at("id")));

            visitTime[index] =
                place.at("visit_time_minutes").get<int>();

            costs[index] =
                place.at("cost").get<int>();

            ratings[index] =
                place.at("rating").get<double>();

            weatherSensitive[index] =
                place.at("weather_sensitive").get<bool>();

            const std::string type =
                place.at("type").get<std::string>();

            auto typeIt = typeIndex.find(type);

            if (typeIt == typeIndex.end()) {
                const int newType =
                    static_cast<int>(typeIndex.size());

                typeIt = typeIndex.emplace(
                    type,
                    newType
                ).first;
            }

            typeId[index] = typeIt->second;
        }

        for (int i = 0; i < n; ++i) {
            const std::string weather =
                secondResponses[static_cast<size_t>(i) + 2]
                    .at("weather")
                    .get<std::string>();

            badWeather[i] =
                weatherSensitive[i] &&
                (weather == "rainy" || weather == "windy");
        }

        // Сопоставляем строки матрицы через echoed ids.
        std::vector<int> matrixRow(n + 1, -1);

        const json& matrixIds = matrixResponse.at("ids");

        for (int row = 0;
             row < static_cast<int>(matrixIds.size());
             ++row) {
            const std::string id =
                idToString(matrixIds[row]);

            if (id == startId) {
                matrixRow[n] = row;
                continue;
            }

            const auto it = idIndex.find(id);

            if (it != idIndex.end()) {
                matrixRow[it->second] = row;
            }
        }

        // Плоский массив быстрее vector<vector<int>>.
        const int matrixSize = n + 1;

        std::vector<int> travelTime(
            static_cast<size_t>(matrixSize) * matrixSize
        );

        const json& matrix = matrixResponse.at("matrix");

        for (int from = 0; from <= n; ++from) {
            for (int to = 0; to <= n; ++to) {
                travelTime[
                    static_cast<size_t>(from) * matrixSize + to
                ] = matrix
                        .at(matrixRow[from])
                        .at(matrixRow[to])
                        .get<int>();
            }
        }

        const auto travel = [&](int from, int to) -> int {
            return travelTime[
                static_cast<size_t>(from) * matrixSize + to
            ];
        };

        // ====================================================
        // Held-Karp DP
        // ====================================================

        const int stateCount = 1 << n;
        const int allPlacesMask = stateCount - 1;

        constexpr int INF =
            std::numeric_limits<int>::max() / 4;

        /*
         * dp[mask][last] — минимальное время в пути для маршрута,
         * который посетил mask и завершился в last.
         *
         * Время в пути целое, поэтому double здесь не нужен.
         */
        std::vector<int> dp(
            static_cast<size_t>(stateCount) * n,
            INF
        );

        std::vector<int8_t> parent(
            static_cast<size_t>(stateCount) * n,
            -1
        );

        std::vector<int> visitSum(stateCount, 0);
        std::vector<int> costSum(stateCount, 0);

        std::vector<uint32_t> typeMask(stateCount, 0);
        std::vector<double> baseScore(stateCount, 0.0);

        /*
         * Сразу вычисляем статическую часть score:
         *
         * rating_sum * rating_weight
         * + diversity * diversity_weight
         * - bad_weather_count * bad_weather_penalty
         */
        for (int mask = 1; mask < stateCount; ++mask) {
            const int place =
                __builtin_ctz(static_cast<unsigned>(mask));

            const int previousMask =
                mask & (mask - 1);

            visitSum[mask] =
                visitSum[previousMask] + visitTime[place];

            costSum[mask] =
                costSum[previousMask] + costs[place];

            const uint32_t currentTypeBit =
                uint32_t{1} << typeId[place];

            const bool isNewType =
                (typeMask[previousMask] &
                 currentTypeBit) == 0;

            typeMask[mask] =
                typeMask[previousMask] | currentTypeBit;

            baseScore[mask] =
                baseScore[previousMask] +
                ratings[place] * ratingWeight -
                (badWeather[place]
                     ? badWeatherPenalty
                     : 0.0) +
                (isNewType
                     ? diversityWeight
                     : 0.0);
        }

        // Маршруты из одного места.
        for (int place = 0; place < n; ++place) {
            const int mask = 1 << place;
            const int initialTravel = travel(n, place);

            if (costs[place] <= budget &&
                initialTravel + visitTime[place] <=
                    timeLimit) {
                dp[
                    static_cast<size_t>(mask) * n + place
                ] = initialTravel;
            }
        }

        double bestScore = 0.0;
        int bestMask = 0;
        int bestLast = -1;

        for (int mask = 1; mask < stateCount; ++mask) {
            if (costSum[mask] > budget ||
                visitSum[mask] > timeLimit) {
                continue;
            }

            // Перебираем только last, входящие в mask.
            for (int lastBits = mask;
                 lastBits != 0;
                 lastBits &= lastBits - 1) {
                const int last =
                    __builtin_ctz(
                        static_cast<unsigned>(lastBits)
                    );

                const size_t currentIndex =
                    static_cast<size_t>(mask) * n + last;

                const int currentTravel =
                    dp[currentIndex];

                if (currentTravel == INF ||
                    currentTravel + visitSum[mask] >
                        timeLimit) {
                    continue;
                }

                const double score =
                    baseScore[mask] -
                    currentTravel * travelPenalty;

                if (score > bestScore) {
                    bestScore = score;
                    bestMask = mask;
                    bestLast = last;
                }

                // Перебираем только ещё не посещённые места.
                int remaining =
                    allPlacesMask ^ mask;

                while (remaining != 0) {
                    const int next =
                        __builtin_ctz(
                            static_cast<unsigned>(remaining)
                        );

                    remaining &= remaining - 1;

                    if (costSum[mask] + costs[next] >
                        budget) {
                        continue;
                    }

                    const int nextTravel =
                        currentTravel + travel(last, next);

                    if (nextTravel +
                            visitSum[mask] +
                            visitTime[next] >
                        timeLimit) {
                        continue;
                    }

                    const int nextMask =
                        mask | (1 << next);

                    const size_t nextIndex =
                        static_cast<size_t>(nextMask) * n +
                        next;

                    if (nextTravel < dp[nextIndex]) {
                        dp[nextIndex] = nextTravel;
                        parent[nextIndex] =
                            static_cast<int8_t>(last);
                    }
                }
            }
        }

        if (bestLast < 0) {
            std::cout << 0 << '\n';
            curl_global_cleanup();
            return 0;
        }

        // ====================================================
        // Восстановление ответа
        // ====================================================

        std::vector<int> route;

        route.reserve(
            __builtin_popcount(
                static_cast<unsigned>(bestMask)
            )
        );

        int currentMask = bestMask;
        int currentPlace = bestLast;

        while (currentPlace >= 0) {
            route.push_back(currentPlace);

            const int previousPlace =
                parent[
                    static_cast<size_t>(currentMask) * n +
                    currentPlace
                ];

            currentMask ^= 1 << currentPlace;
            currentPlace = previousPlace;
        }

        std::reverse(route.begin(), route.end());

        std::cout << route.size() << '\n';

        for (size_t i = 0; i < route.size(); ++i) {
            if (i != 0) {
                std::cout << ' ';
            }

            std::cout << ids[route[i]];
        }

        std::cout << '\n';
    } catch (...) {
        // Для некорректного или недоступного API сохраняем
        // корректный формат ответа.
        std::cout << 0 << '\n';
    }

    curl_global_cleanup();
    return 0;
}

Что изменилось

n + 4 последовательных HTTP-запроса заменены на две параллельные волны.
Время, стоимость и DP хранятся как int, а не double.
Матрица пути хранится в одном непрерывном массиве.
Циклы перебирают только установленные и неустановленные биты маски.
Невозможные переходы отсекаются до записи в DP.
rating_sum и bad_weather_count больше не хранятся отдельно: статическая часть оценки вычисляется рекуррентно.
Порядок элементов в ответе /places/batch больше не предполагается совпадающим с порядком запроса.

Сложность остаётся O(n² · 2ⁿ), память — O(n · 2ⁿ), но при n ≤ 16 основное ускорение должно прийти именно от параллельного обращения к API.

Answer 2

javascript
'use strict';

const fs = require('fs');
const http = require('http');
const https = require('https');

const NEG = -1_000_000_000;

const input = fs.readFileSync(0, 'utf8')
    .split(/\r?\n/)
    .map(line => line.trim())
    .filter(Boolean);

const baseUrl = input[0] ?? '';
const tourId = input[1] ?? '';

const httpAgent = new http.Agent({
    keepAlive: true,
    maxSockets: 8,
});

const httpsAgent = new https.Agent({
    keepAlive: true,
    maxSockets: 8,
});

function getJson(path) {
    return new Promise((resolve, reject) => {
        const url = new URL(path, baseUrl);
        const client = url.protocol === 'https:' ? https : http;
        const agent = url.protocol === 'https:' ? httpsAgent : httpAgent;

        const request = client.get(
            url,
            {
                agent,
                timeout: 4500,
                headers: {
                    Accept: 'application/json',
                },
            },
            response => {
                const chunks = [];

                response.on('data', chunk => {
                    chunks.push(chunk);
                });

                response.on('end', () => {
                    if (
                        response.statusCode === undefined ||
                        response.statusCode < 200 ||
                        response.statusCode >= 300
                    ) {
                        reject(
                            new Error(
                                `HTTP error: ${response.statusCode}`
                            )
                        );
                        return;
                    }

                    try {
                        const body = Buffer.concat(chunks).toString('utf8');
                        resolve(JSON.parse(body));
                    } catch (error) {
                        reject(error);
                    }
                });
            }
        );

        request.on('timeout', () => {
            request.destroy(new Error('HTTP timeout'));
        });

        request.on('error', reject);
    });
}

function idKey(value) {
    return String(value);
}

function mergeDp(left, right, limit) {
    const maxLeft = Math.min(limit, left.length - 1);
    const maxRight = Math.min(limit, right.length - 1);
    const maxResult = Math.min(limit, maxLeft + maxRight);

    const result = new Int32Array(maxResult + 1);
    result.fill(NEG);

    for (let leftCount = 0; leftCount <= maxLeft; ++leftCount) {
        const leftValue = left[leftCount];

        if (leftValue === NEG) {
            continue;
        }

        const rightLimit = Math.min(
            maxRight,
            limit - leftCount
        );

        for (
            let rightCount = 0;
            rightCount <= rightLimit;
            ++rightCount
        ) {
            const rightValue = right[rightCount];

            if (rightValue === NEG) {
                continue;
            }

            const count = leftCount + rightCount;
            const value = leftValue + rightValue;

            if (value > result[count]) {
                result[count] = value;
            }
        }
    }

    return result;
}

async function main() {
    /*
     * Все три запроса независимы, поэтому выполняем их
     * одновременно.
     */
    const [tourResponse, routesResponse, stampsResponse] =
        await Promise.all([
            getJson(`/tour/${encodeURIComponent(tourId)}`),
            getJson(
                `/routes?tour_id=${encodeURIComponent(tourId)}`
            ),
            getJson(
                `/stamps?tour_id=${encodeURIComponent(tourId)}`
            ),
        ]);

    const startIsland = idKey(tourResponse.start_island);

    let maxStamps = Number(tourResponse.max_stamps);

    const rawRoutes = routesResponse.routes ?? [];
    const rawStamps = stampsResponse.stamps ?? [];

    const stampCount = rawStamps.length;

    maxStamps = Math.min(maxStamps, stampCount);

    if (maxStamps <= 0 || stampCount === 0) {
        process.stdout.write('0\n');
        return;
    }

    // ========================================================
    // Достижимые острова
    // ========================================================

    const islandGraph = new Map();

    function ensureIsland(island) {
        if (!islandGraph.has(island)) {
            islandGraph.set(island, []);
        }
    }

    ensureIsland(startIsland);

    for (const route of rawRoutes) {
        const from = idKey(route.from);
        const to = idKey(route.to);

        ensureIsland(from);
        ensureIsland(to);

        islandGraph.get(from).push(to);
    }

    for (const stamp of rawStamps) {
        ensureIsland(idKey(stamp.island_id));
    }

    const reachable = new Set([startIsland]);
    const islandStack = [startIsland];

    while (islandStack.length > 0) {
        const island = islandStack.pop();
        const neighbours = islandGraph.get(island) ?? [];

        for (const next of neighbours) {
            if (!reachable.has(next)) {
                reachable.add(next);
                islandStack.push(next);
            }
        }
    }

    // ========================================================
    // Лес зависимостей штампов
    // ========================================================

    const nodes = new Array(stampCount);
    const stampIndex = new Map();

    for (let i = 0; i < stampCount; ++i) {
        const rawStamp = rawStamps[i];
        const stampId = idKey(rawStamp.stamp_id);

        nodes[i] = {
            id: stampId,
            island: idKey(rawStamp.island_id),
            rarity: Number(rawStamp.rarity),
            children: [],
            dp: null,
            prefix: null,
        };

        stampIndex.set(stampId, i);
    }

    const parent = new Int32Array(stampCount);
    parent.fill(-1);

    /*
     * dependencyChildren хранит полный лес, включая пока
     * недоступные вершины. Он нужен для распространения
     * недоступности на зависимые штампы.
     */
    const dependencyChildren = Array.from(
        { length: stampCount },
        () => []
    );

    const blocked = new Uint8Array(stampCount);

    for (let i = 0; i < stampCount; ++i) {
        const rawStamp = rawStamps[i];

        if (!reachable.has(nodes[i].island)) {
            blocked[i] = 1;
        }

        const requirements = Array.isArray(rawStamp.requires)
            ? rawStamp.requires
            : [];

        if (requirements.length === 0) {
            continue;
        }

        const requiredId = idKey(requirements[0]);
        const requiredIndex = stampIndex.get(requiredId);

        if (requiredIndex === undefined) {
            blocked[i] = 1;
            continue;
        }

        parent[i] = requiredIndex;
        dependencyChildren[requiredIndex].push(i);
    }

    /*
     * Если требуемый штамп недоступен, все зависящие от него
     * штампы также недоступны.
     */
    const blockedQueue = [];

    for (let i = 0; i < stampCount; ++i) {
        if (blocked[i]) {
            blockedQueue.push(i);
        }
    }

    for (
        let queueHead = 0;
        queueHead < blockedQueue.length;
        ++queueHead
    ) {
        const vertex = blockedQueue[queueHead];

        for (const child of dependencyChildren[vertex]) {
            if (!blocked[child]) {
                blocked[child] = 1;
                blockedQueue.push(child);
            }
        }
    }

    const roots = [];
    let availableCount = 0;

    for (let i = 0; i < stampCount; ++i) {
        if (blocked[i]) {
            continue;
        }

        ++availableCount;

        if (parent[i] === -1) {
            roots.push(i);
        } else {
            nodes[parent[i]].children.push(i);
        }
    }

    if (availableCount === 0) {
        process.stdout.write('0\n');
        return;
    }

    maxStamps = Math.min(maxStamps, availableCount);

    // ========================================================
    // DP по деревьям
    // ========================================================

    /*
     * dp[x] — максимальная редкость при выборе ровно x
     * штампов из поддерева.
     *
     * При x > 0 корень поддерева обязательно выбран.
     */
    function buildDp(vertex) {
        const node = nodes[vertex];

        for (const child of node.children) {
            buildDp(child);
        }

        let merged = new Int32Array(1);
        merged[0] = 0;

        node.prefix = [];

        for (const child of node.children) {
            /*
             * Сохраняем состояние до добавления ребёнка,
             * чтобы затем восстановить ответ.
             */
            node.prefix.push(merged);

            // Одно место должно остаться для текущей вершины.
            merged = mergeDp(
                merged,
                nodes[child].dp,
                maxStamps - 1
            );
        }

        const maxTake = Math.min(
            maxStamps,
            merged.length
        );

        const dp = new Int32Array(maxTake + 1);
        dp.fill(NEG);
        dp[0] = 0;

        const maxFromChildren = Math.min(
            merged.length - 1,
            maxStamps - 1
        );

        for (
            let fromChildren = 0;
            fromChildren <= maxFromChildren;
            ++fromChildren
        ) {
            if (merged[fromChildren] === NEG) {
                continue;
            }

            dp[fromChildren + 1] =
                node.rarity + merged[fromChildren];
        }

        node.dp = dp;
    }

    for (const root of roots) {
        buildDp(root);
    }

    // Объединяем независимые деревья леса.
    let totalDp = new Int32Array(1);
    totalDp[0] = 0;

    const rootPrefix = [];

    for (const root of roots) {
        rootPrefix.push(totalDp);

        totalDp = mergeDp(
            totalDp,
            nodes[root].dp,
            maxStamps
        );
    }

    /*
     * Редкости положительные, поэтому обычно оптимально взять
     * maxStamps штампов. Тем не менее ищем максимум явно.
     */
    let bestCount = 0;
    let bestValue = 0;

    for (
        let count = 1;
        count < totalDp.length &&
        count <= maxStamps;
        ++count
    ) {
        if (totalDp[count] > bestValue) {
            bestValue = totalDp[count];
            bestCount = count;
        }
    }

    if (bestCount === 0) {
        process.stdout.write('0\n');
        return;
    }

    // ========================================================
    // Восстановление ответа
    // ========================================================

    const answer = [];

    function restoreIndependentTrees(
        treeRoots,
        prefix,
        takeCount,
        targetValue
    ) {
        for (
            let i = treeRoots.length - 1;
            i >= 0;
            --i
        ) {
            const root = treeRoots[i];
            const previousDp = prefix[i];
            const rootDp = nodes[root].dp;

            const maxFromRoot = Math.min(
                takeCount,
                rootDp.length - 1
            );

            let chosenFromRoot = -1;

            for (
                let fromRoot = 0;
                fromRoot <= maxFromRoot;
                ++fromRoot
            ) {
                const fromPrevious =
                    takeCount - fromRoot;

                if (
                    fromPrevious < 0 ||
                    fromPrevious >= previousDp.length
                ) {
                    continue;
                }

                if (
                    previousDp[fromPrevious] === NEG ||
                    rootDp[fromRoot] === NEG
                ) {
                    continue;
                }

                if (
                    previousDp[fromPrevious] +
                        rootDp[fromRoot] ===
                    targetValue
                ) {
                    chosenFromRoot = fromRoot;
                    break;
                }
            }

            if (chosenFromRoot < 0) {
                throw new Error('DP reconstruction failed');
            }

            takeCount -= chosenFromRoot;
            targetValue = previousDp[takeCount];

            if (chosenFromRoot > 0) {
                restoreNode(root, chosenFromRoot);
            }
        }
    }

    function restoreNode(vertex, takeCount) {
        const node = nodes[vertex];

        /*
         * Сначала выводим текущий штамп, затем штампы
         * из поддеревьев. Поэтому требование всегда будет
         * раньше зависимого штампа.
         */
        answer.push(node.id);

        restoreIndependentTrees(
            node.children,
            node.prefix,
            takeCount - 1,
            node.dp[takeCount] - node.rarity
        );
    }

    restoreIndependentTrees(
        roots,
        rootPrefix,
        bestCount,
        totalDp[bestCount]
    );

    process.stdout.write(
        `${answer.length}\n${answer.join(' ')}\n`
    );
}

main()
    .catch(() => {
        process.stdout.write('0\n');
    })
    .finally(() => {
        httpAgent.destroy();
        httpsAgent.destroy();
    });

Сложность алгоритма — O(number_of_stamps · max_stamps²), память — O(number_of_stamps · max_stamps).

Answer 3

Below is an optimized C11 implementation. The algorithm remains O(n·m), which is asymptotically optimal because every cell must be read.

c
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define INPUT_BUFFER_SIZE (1u << 20)

typedef struct {
    unsigned char data[INPUT_BUFFER_SIZE];
    size_t position;
    size_t length;
} FastInput;

static inline int next_char(FastInput *input) {
    if (input->position == input->length) {
        input->length = fread(
            input->data,
            1,
            INPUT_BUFFER_SIZE,
            stdin
        );
        input->position = 0;

        if (input->length == 0) {
            return EOF;
        }
    }

    return input->data[input->position++];
}

static int read_int(FastInput *input) {
    int c;

    do {
        c = next_char(input);
    } while (c <= ' ' && c != EOF);

    int value = 0;

    while (c >= '0' && c <= '9') {
        value = value * 10 + (c - '0');
        c = next_char(input);
    }

    return value;
}

/*
 * Cells are encoded as:
 *
 * 0 = type 1: clean, increases k
 * 1 = type 2: clean, increases p
 * 2 = type 3: dirty, increases k
 * 3 = type 4: dirty, increases p
 *
 * Therefore:
 *     cell & 1  -> increases p
 *     cell >> 1 -> initially dirty
 */
static void read_row(
    FastInput *input,
    uint8_t *destination,
    int length
) {
    int c;

    do {
        c = next_char(input);
    } while (c <= ' ' && c != EOF);

    destination[0] = (uint8_t)(c - '1');

    for (int j = 1; j < length; ++j) {
        destination[j] =
            (uint8_t)(next_char(input) - '1');
    }
}

static void solve_test(
    FastInput *input,
    char **output_position
) {
    const int n = read_int(input);
    const int m = read_int(input);

    const size_t cell_count =
        (size_t)n * (size_t)m;

    /*
     * grid: 1 byte per cell.
     *
     * column_suffix[i*m+j] is the number of initially dirty
     * cells in column j on rows i..n-1.
     *
     * Since n <= 3000, uint16_t is sufficient.
     */
    uint8_t *grid = malloc(
        cell_count * sizeof(*grid)
    );

    uint16_t *column_suffix = malloc(
        cell_count * sizeof(*column_suffix)
    );

    uint16_t *column_count = calloc(
        (size_t)m,
        sizeof(*column_count)
    );

    uint16_t *row_suffix = malloc(
        ((size_t)m + 1) * sizeof(*row_suffix)
    );

    /*
     * p cannot exceed n+m-1 <= 5999, so int16_t is enough.
     * -1 means that the state is unreachable.
     */
    int16_t *current = malloc(
        (size_t)m * sizeof(*current)
    );

    int16_t *next = malloc(
        (size_t)m * sizeof(*next)
    );

    if (
        grid == NULL ||
        column_suffix == NULL ||
        column_count == NULL ||
        row_suffix == NULL ||
        current == NULL ||
        next == NULL
    ) {
        free(grid);
        free(column_suffix);
        free(column_count);
        free(row_suffix);
        free(current);
        free(next);

        memcpy(*output_position, "No\n", 3);
        *output_position += 3;
        return;
    }

    for (int i = 0; i < n; ++i) {
        read_row(
            input,
            grid + (size_t)i * m,
            m
        );
    }

    /*
     * Build dirty-cell suffix sums for every column.
     */
    for (int i = n - 1; i >= 0; --i) {
        const size_t row_base =
            (size_t)i * m;

        for (int j = 0; j < m; ++j) {
            column_count[j] +=
                (uint16_t)(grid[row_base + j] >> 1);

            column_suffix[row_base + j] =
                column_count[j];
        }
    }

    free(column_count);

    memset(
        current,
        0xFF,
        (size_t)m * sizeof(*current)
    );

    /*
     * The effect of cell (1,1) is applied immediately.
     */
    current[0] = (int16_t)(grid[0] & 1);

    for (int i = 0; i < n; ++i) {
        memset(
            next,
            0xFF,
            (size_t)m * sizeof(*next)
        );

        const size_t row_base =
            (size_t)i * m;

        row_suffix[m] = 0;

        for (int j = m - 1; j >= 0; --j) {
            row_suffix[j] =
                (uint16_t)(
                    row_suffix[j + 1] +
                    (grid[row_base + j] >> 1)
                );
        }

        for (int j = 0; j < m; ++j) {
            const int power = current[j];

            if (power < 0) {
                continue;
            }

            /*
             * At (i,j), using zero-based coordinates:
             *
             * visited cells = i + j + 1
             *
             * k = 1 + number of k-increasing cells
             *   = 1 + visited cells - p
             *   = i + j + 2 - p
             */

            /*
             * Move right.
             *
             * The brush covers column j down to:
             *
             * i + k - 1
             *
             * Therefore the first cell not covered by the
             * current brush is:
             *
             * first_below = i + k
             *             = 2*i + j + 2 - p
             */
            if (j + 1 < m) {
                const int first_below =
                    2 * i + j + 2 - power;

                int dirty_below = 0;

                if (first_below < n) {
                    dirty_below =
                        column_suffix[
                            (size_t)first_below * m + j
                        ];
                }

                /*
                 * The column laser can clean at most p dirty
                 * cells left below the brush.
                 */
                if (dirty_below <= power) {
                    const int new_power =
                        power +
                        (grid[row_base + j + 1] & 1);

                    if (new_power > current[j + 1]) {
                        current[j + 1] =
                            (int16_t)new_power;
                    }
                }
            }

            /*
             * Move down.
             *
             * The first cell in the current row not covered
             * by the brush is:
             *
             * first_right = j + k
             *             = i + 2*j + 2 - p
             */
            if (i + 1 < n) {
                int first_right =
                    i + 2 * j + 2 - power;

                if (first_right > m) {
                    first_right = m;
                }

                const int dirty_right =
                    row_suffix[first_right];

                /*
                 * The row laser can clean at most p dirty
                 * cells left to the right of the brush.
                 */
                if (dirty_right <= power) {
                    const int new_power =
                        power +
                        (
                            grid[
                                row_base + (size_t)m + j
                            ] & 1
                        );

                    if (new_power > next[j]) {
                        next[j] =
                            (int16_t)new_power;
                    }
                }
            }
        }

        if (i + 1 < n) {
            int16_t *temporary = current;
            current = next;
            next = temporary;
        }
    }

    if (current[m - 1] >= 0) {
        memcpy(*output_position, "Yes\n", 4);
        *output_position += 4;
    } else {
        memcpy(*output_position, "No\n", 3);
        *output_position += 3;
    }

    free(grid);
    free(column_suffix);
    free(row_suffix);
    free(current);
    free(next);
}

int main(void) {
    FastInput input = {
        .position = 0,
        .length = 0
    };

    const int test_count = read_int(&input);

    /*
     * Each answer occupies at most 4 bytes: "Yes\n".
     */
    char *output = malloc(
        (size_t)test_count * 4 + 1
    );

    if (output == NULL) {
        return 0;
    }

    char *output_position = output;

    for (int test = 0; test < test_count; ++test) {
        solve_test(
            &input,
            &output_position
        );
    }

    fwrite(
        output,
        1,
        (size_t)(output_position - output),
        stdout
    );

    free(output);
    return 0;
}

Optimizations applied

Uses buffered fread instead of scanf.
Encodes each cell in one byte:
- cell & 1 means that it increases p;
- cell >> 1 means that it is dirty.
Uses uint16_t for dirty-cell suffix counts.
Uses int16_t for DP states because p ≤ n + m - 1 ≤ 5999.
Uses contiguous arrays and row-major access.
Replaces repeated brush-size calculations with direct formulas for the first uncovered row or column.
Keeps only the maximum reachable p for each position.

Keeping only maximum p is valid: when p increases by one, k decreases by one, so at most one additional cell becomes uncovered in the relevant row or column, while the laser capacity also increases by one.

Complexity: O(n·m) time and approximately 3·n·m bytes of memory.

Answer 4

Ниже оптимизированная версия на C11. В ней нет STL, хеш-таблиц и многочисленных мелких выделений памяти. Для сортировки кандидатов Manhattan MST используется radix sort, а KD-дерево дополнено ограничивающими прямоугольниками.

c
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define INPUT_BUFFER_SIZE (1u << 20)
#define OUTPUT_BUFFER_SIZE (1u << 20)

#define RADIX_BITS 11
#define RADIX_SIZE (1u << RADIX_BITS)
#define RADIX_MASK (RADIX_SIZE - 1u)

typedef int64_t i64;
typedef uint64_t u64;
typedef uint32_t u32;

typedef struct {
    u32 distance;
    int from;
    int to;
} Edge;

/* ============================================================
 * Fast input
 * ============================================================ */

static unsigned char input_buffer[INPUT_BUFFER_SIZE];
static size_t input_position = 0;
static size_t input_length = 0;

static inline int next_char(void) {
    if (input_position == input_length) {
        input_length = fread(
            input_buffer,
            1,
            sizeof(input_buffer),
            stdin
        );

        input_position = 0;

        if (input_length == 0) {
            return EOF;
        }
    }

    return input_buffer[input_position++];
}

static inline i64 read_i64(void) {
    int c = next_char();

    while (c <= ' ' && c != EOF) {
        c = next_char();
    }

    i64 value = 0;

    while (c >= '0' && c <= '9') {
        value = value * 10 + (c - '0');
        c = next_char();
    }

    return value;
}

/* ============================================================
 * Fast output
 * ============================================================ */

static char output_buffer[OUTPUT_BUFFER_SIZE];
static size_t output_position = 0;

static inline void flush_output(void) {
    if (output_position != 0) {
        fwrite(
            output_buffer,
            1,
            output_position,
            stdout
        );

        output_position = 0;
    }
}

static inline void write_char(char c) {
    if (output_position == OUTPUT_BUFFER_SIZE) {
        flush_output();
    }

    output_buffer[output_position++] = c;
}

static inline void write_u64(u64 value) {
    char buffer[24];
    int length = 0;

    do {
        buffer[length++] =
            (char)('0' + value % 10);

        value /= 10;
    } while (value != 0);

    while (length != 0) {
        write_char(buffer[--length]);
    }
}

static inline void write_int(int value) {
    char buffer[16];
    int length = 0;
    u32 current = (u32)value;

    do {
        buffer[length++] =
            (char)('0' + current % 10u);

        current /= 10u;
    } while (current != 0);

    while (length != 0) {
        write_char(buffer[--length]);
    }
}

/* ============================================================
 * Reusable workspace
 * ============================================================ */

static int capacity = 0;

static i64 *point_x;
static i64 *point_y;
static i64 *point_radius;

static i64 *point_u;
static i64 *point_v;

static i64 *kd_min_u;
static i64 *kd_max_u;
static i64 *kd_min_v;
static i64 *kd_max_v;

static int *global_parent;
static int *kd_order;

static int *class_count;
static int *class_start;
static int *class_cursor;
static int *class_members;

static i64 *local_x;
static i64 *local_y;

static u64 *sort_key;
static int *sort_index;
static int *sort_temporary;

static int *rank_x;
static int *rank_y;

static i64 *fenwick_value;
static int *fenwick_id;
static int *fenwick_stamp;
static int fenwick_epoch = 0;

static int *local_parent;

static Edge *candidate_edges;
static Edge *temporary_edges;

static int *answer_from;
static int *answer_to;

static u32 radix_count[RADIX_SIZE];

static void *checked_realloc(
    void *pointer,
    size_t byte_count
) {
    void *result = realloc(pointer, byte_count);

    if (result == NULL) {
        exit(0);
    }

    return result;
}

#define RESIZE(pointer, type, count)                        \
    do {                                                    \
        (pointer) = (type *)checked_realloc(                \
            (pointer),                                      \
            sizeof(type) * (size_t)(count)                  \
        );                                                  \
    } while (0)

static void ensure_capacity(int required) {
    if (required <= capacity) {
        return;
    }

    int new_capacity = capacity != 0 ? capacity : 1;

    while (new_capacity < required) {
        new_capacity <<= 1;
    }

    capacity = new_capacity;

    RESIZE(point_x, i64, capacity);
    RESIZE(point_y, i64, capacity);
    RESIZE(point_radius, i64, capacity);

    RESIZE(point_u, i64, capacity);
    RESIZE(point_v, i64, capacity);

    RESIZE(kd_min_u, i64, capacity);
    RESIZE(kd_max_u, i64, capacity);
    RESIZE(kd_min_v, i64, capacity);
    RESIZE(kd_max_v, i64, capacity);

    RESIZE(global_parent, int, capacity);
    RESIZE(kd_order, int, capacity);

    RESIZE(class_count, int, capacity);
    RESIZE(class_start, int, capacity + 1);
    RESIZE(class_cursor, int, capacity);
    RESIZE(class_members, int, capacity);

    RESIZE(local_x, i64, capacity);
    RESIZE(local_y, i64, capacity);

    RESIZE(sort_key, u64, capacity);
    RESIZE(sort_index, int, capacity);
    RESIZE(sort_temporary, int, capacity);

    RESIZE(rank_x, int, capacity);
    RESIZE(rank_y, int, capacity);

    RESIZE(fenwick_value, i64, capacity + 1);
    RESIZE(fenwick_id, int, capacity + 1);
    RESIZE(fenwick_stamp, int, capacity + 1);

    RESIZE(local_parent, int, capacity);

    RESIZE(
        candidate_edges,
        Edge,
        (size_t)capacity * 8u
    );

    RESIZE(
        temporary_edges,
        Edge,
        (size_t)capacity * 8u
    );

    RESIZE(answer_from, int, capacity);
    RESIZE(answer_to, int, capacity);

    memset(
        fenwick_stamp,
        0,
        sizeof(int) * (size_t)(capacity + 1)
    );

    fenwick_epoch = 0;
}

/* ============================================================
 * Global DSU
 * ============================================================ */

static inline int global_find(int vertex) {
    int root = vertex;

    while (global_parent[root] >= 0) {
        root = global_parent[root];
    }

    while (vertex != root) {
        int parent = global_parent[vertex];

        global_parent[vertex] = root;
        vertex = parent;
    }

    return root;
}

static inline void global_union(
    int first,
    int second
) {
    first = global_find(first);
    second = global_find(second);

    if (first == second) {
        return;
    }

    if (global_parent[first] > global_parent[second]) {
        int temporary = first;
        first = second;
        second = temporary;
    }

    global_parent[first] += global_parent[second];
    global_parent[second] = first;
}

/* ============================================================
 * KD tree
 * ============================================================ */

static u32 random_state = 2463534242u;

static inline u32 next_random(void) {
    u32 value = random_state;

    value ^= value << 13;
    value ^= value >> 17;
    value ^= value << 5;

    random_state = value;
    return value;
}

static inline void swap_int(
    int *first,
    int *second
) {
    int temporary = *first;
    *first = *second;
    *second = temporary;
}

static inline int kd_less(
    int first,
    int second,
    int axis
) {
    const i64 first_coordinate =
        axis ? point_v[first] : point_u[first];

    const i64 second_coordinate =
        axis ? point_v[second] : point_u[second];

    if (first_coordinate != second_coordinate) {
        return first_coordinate < second_coordinate;
    }

    const i64 first_secondary =
        axis ? point_u[first] : point_v[first];

    const i64 second_secondary =
        axis ? point_u[second] : point_v[second];

    if (first_secondary != second_secondary) {
        return first_secondary < second_secondary;
    }

    return first < second;
}

static void kd_select(
    int left,
    int right,
    int target,
    int axis
) {
    while (right - left > 1) {
        const int pivot_position =
            left +
            (int)(
                next_random() %
                (u32)(right - left)
            );

        const int pivot =
            kd_order[pivot_position];

        swap_int(
            &kd_order[pivot_position],
            &kd_order[right - 1]
        );

        int store = left;

        for (int i = left; i < right - 1; ++i) {
            if (kd_less(kd_order[i], pivot, axis)) {
                swap_int(
                    &kd_order[i],
                    &kd_order[store]
                );

                ++store;
            }
        }

        swap_int(
            &kd_order[store],
            &kd_order[right - 1]
        );

        if (store == target) {
            return;
        }

        if (target < store) {
            right = store;
        } else {
            left = store + 1;
        }
    }
}

static void build_kd_tree(
    int left,
    int right,
    int depth
) {
    if (left >= right) {
        return;
    }

    const int middle = (left + right) >> 1;

    kd_select(
        left,
        right,
        middle,
        depth & 1
    );

    build_kd_tree(
        left,
        middle,
        depth + 1
    );

    build_kd_tree(
        middle + 1,
        right,
        depth + 1
    );

    const int point = kd_order[middle];

    i64 minimum_u = point_u[point];
    i64 maximum_u = point_u[point];
    i64 minimum_v = point_v[point];
    i64 maximum_v = point_v[point];

    if (left < middle) {
        const int child = (left + middle) >> 1;

        if (kd_min_u[child] < minimum_u) {
            minimum_u = kd_min_u[child];
        }

        if (kd_max_u[child] > maximum_u) {
            maximum_u = kd_max_u[child];
        }

        if (kd_min_v[child] < minimum_v) {
            minimum_v = kd_min_v[child];
        }

        if (kd_max_v[child] > maximum_v) {
            maximum_v = kd_max_v[child];
        }
    }

    if (middle + 1 < right) {
        const int child =
            (middle + 1 + right) >> 1;

        if (kd_min_u[child] < minimum_u) {
            minimum_u = kd_min_u[child];
        }

        if (kd_max_u[child] > maximum_u) {
            maximum_u = kd_max_u[child];
        }

        if (kd_min_v[child] < minimum_v) {
            minimum_v = kd_min_v[child];
        }

        if (kd_max_v[child] > maximum_v) {
            maximum_v = kd_max_v[child];
        }
    }

    kd_min_u[middle] = minimum_u;
    kd_max_u[middle] = maximum_u;
    kd_min_v[middle] = minimum_v;
    kd_max_v[middle] = maximum_v;
}

static i64 query_min_u;
static i64 query_max_u;
static i64 query_min_v;
static i64 query_max_v;
static int query_center;

static void query_kd_tree(
    int left,
    int right
) {
    if (left >= right) {
        return;
    }

    const int middle = (left + right) >> 1;

    if (
        kd_max_u[middle] < query_min_u ||
        kd_min_u[middle] > query_max_u ||
        kd_max_v[middle] < query_min_v ||
        kd_min_v[middle] > query_max_v
    ) {
        return;
    }

    if (
        query_min_u <= kd_min_u[middle] &&
        kd_max_u[middle] <= query_max_u &&
        query_min_v <= kd_min_v[middle] &&
        kd_max_v[middle] <= query_max_v
    ) {
        for (int i = left; i < right; ++i) {
            global_union(
                query_center,
                kd_order[i]
            );
        }

        return;
    }

    const int point = kd_order[middle];

    if (
        query_min_u <= point_u[point] &&
        point_u[point] <= query_max_u &&
        query_min_v <= point_v[point] &&
        point_v[point] <= query_max_v
    ) {
        global_union(query_center, point);
    }

    query_kd_tree(left, middle);
    query_kd_tree(middle + 1, right);
}

/* ============================================================
 * Radix sorting
 * ============================================================ */

static int *radix_sort_coordinates(
    const i64 *values,
    int count,
    int *first,
    int *second
) {
    if (count < 32) {
        for (int i = 1; i < count; ++i) {
            const int current = first[i];
            const u32 key = (u32)values[current];

            int j = i - 1;

            while (
                j >= 0 &&
                (u32)values[first[j]] > key
            ) {
                first[j + 1] = first[j];
                --j;
            }

            first[j + 1] = current;
        }

        return first;
    }

    int *source = first;
    int *destination = second;

    for (
        int shift = 0;
        shift < 32;
        shift += RADIX_BITS
    ) {
        memset(
            radix_count,
            0,
            sizeof(radix_count)
        );

        for (int i = 0; i < count; ++i) {
            const u32 bucket =
                (
                    (u32)values[source[i]] >>
                    shift
                ) & RADIX_MASK;

            ++radix_count[bucket];
        }

        u32 prefix = 0;

        for (u32 i = 0; i < RADIX_SIZE; ++i) {
            const u32 amount = radix_count[i];
            radix_count[i] = prefix;
            prefix += amount;
        }

        for (int i = 0; i < count; ++i) {
            const int id = source[i];

            const u32 bucket =
                (
                    (u32)values[id] >>
                    shift
                ) & RADIX_MASK;

            destination[
                radix_count[bucket]++
            ] = id;
        }

        int *temporary = source;
        source = destination;
        destination = temporary;
    }

    return source;
}

static int *radix_sort_keys(
    int count,
    int *first,
    int *second
) {
    if (count < 32) {
        for (int i = 1; i < count; ++i) {
            const int current = first[i];
            const u64 key = sort_key[current];

            int j = i - 1;

            while (
                j >= 0 &&
                sort_key[first[j]] > key
            ) {
                first[j + 1] = first[j];
                --j;
            }

            first[j + 1] = current;
        }

        return first;
    }

    int *source = first;
    int *destination = second;

    for (
        int shift = 0;
        shift < 64;
        shift += RADIX_BITS
    ) {
        memset(
            radix_count,
            0,
            sizeof(radix_count)
        );

        for (int i = 0; i < count; ++i) {
            const u32 bucket =
                (u32)(
                    (
                        sort_key[source[i]] >>
                        shift
                    ) & RADIX_MASK
                );

            ++radix_count[bucket];
        }

        u32 prefix = 0;

        for (u32 i = 0; i < RADIX_SIZE; ++i) {
            const u32 amount = radix_count[i];
            radix_count[i] = prefix;
            prefix += amount;
        }

        for (int i = 0; i < count; ++i) {
            const int id = source[i];

            const u32 bucket =
                (u32)(
                    (
                        sort_key[id] >>
                        shift
                    ) & RADIX_MASK
                );

            destination[
                radix_count[bucket]++
            ] = id;
        }

        int *temporary = source;
        source = destination;
        destination = temporary;
    }

    return source;
}

static Edge *radix_sort_edges(
    Edge *first,
    Edge *second,
    int count
) {
    if (count < 32) {
        for (int i = 1; i < count; ++i) {
            const Edge current = first[i];
            int j = i - 1;

            while (
                j >= 0 &&
                first[j].distance >
                    current.distance
            ) {
                first[j + 1] = first[j];
                --j;
            }

            first[j + 1] = current;
        }

        return first;
    }

    Edge *source = first;
    Edge *destination = second;

    for (
        int shift = 0;
        shift < 32;
        shift += RADIX_BITS
    ) {
        memset(
            radix_count,
            0,
            sizeof(radix_count)
        );

        for (int i = 0; i < count; ++i) {
            const u32 bucket =
                (
                    source[i].distance >>
                    shift
                ) & RADIX_MASK;

            ++radix_count[bucket];
        }

        u32 prefix = 0;

        for (u32 i = 0; i < RADIX_SIZE; ++i) {
            const u32 amount = radix_count[i];
            radix_count[i] = prefix;
            prefix += amount;
        }

        for (int i = 0; i < count; ++i) {
            const u32 bucket =
                (
                    source[i].distance >>
                    shift
                ) & RADIX_MASK;

            destination[
                radix_count[bucket]++
            ] = source[i];
        }

        Edge *temporary = source;
        source = destination;
        destination = temporary;
    }

    return source;
}

/* ============================================================
 * Local DSU and Manhattan MST candidates
 * ============================================================ */

static inline int local_find(int vertex) {
    int root = vertex;

    while (local_parent[root] >= 0) {
        root = local_parent[root];
    }

    while (vertex != root) {
        const int parent = local_parent[vertex];

        local_parent[vertex] = root;
        vertex = parent;
    }

    return root;
}

static inline int local_union(
    int first,
    int second
) {
    first = local_find(first);
    second = local_find(second);

    if (first == second) {
        return 0;
    }

    if (local_parent[first] > local_parent[second]) {
        const int temporary = first;
        first = second;
        second = temporary;
    }

    local_parent[first] += local_parent[second];
    local_parent[second] = first;

    return 1;
}

static inline u32 manhattan_distance(
    int first,
    int second
) {
    i64 dx = local_x[first] - local_x[second];
    i64 dy = local_y[first] - local_y[second];

    if (dx < 0) {
        dx = -dx;
    }

    if (dy < 0) {
        dy = -dy;
    }

    return (u32)(dx + dy);
}

static inline u64 make_descending_key(
    i64 first,
    i64 second
) {
    u32 first_encoded =
        ((u32)(int32_t)first) ^
        0x80000000u;

    u32 second_encoded =
        ((u32)(int32_t)second) ^
        0x80000000u;

    return
        ((u64)(~first_encoded) << 32) |
        (u64)(~second_encoded);
}

static int build_manhattan_candidates(int count) {
    for (int i = 0; i < count; ++i) {
        sort_index[i] = i;
    }

    int *sorted = radix_sort_coordinates(
        local_x,
        count,
        sort_index,
        sort_temporary
    );

    int unique_x = 0;

    for (int i = 0; i < count; ++i) {
        const int id = sorted[i];

        if (
            i == 0 ||
            local_x[id] !=
                local_x[sorted[i - 1]]
        ) {
            ++unique_x;
        }

        rank_x[id] = unique_x - 1;
    }

    for (int i = 0; i < count; ++i) {
        sort_index[i] = i;
    }

    sorted = radix_sort_coordinates(
        local_y,
        count,
        sort_index,
        sort_temporary
    );

    int unique_y = 0;

    for (int i = 0; i < count; ++i) {
        const int id = sorted[i];

        if (
            i == 0 ||
            local_y[id] !=
                local_y[sorted[i - 1]]
        ) {
            ++unique_y;
        }

        rank_y[id] = unique_y - 1;
    }

    int edge_count = 0;

    static const int signs[2] = {
        -1,
        1
    };

    /*
     * Eight transformations cover all Manhattan octants.
     */
    for (int swap_coordinates = 0;
         swap_coordinates < 2;
         ++swap_coordinates) {

        for (int sx_index = 0;
             sx_index < 2;
             ++sx_index) {

            const int sign_x = signs[sx_index];

            for (int sy_index = 0;
                 sy_index < 2;
                 ++sy_index) {

                const int sign_y = signs[sy_index];

                for (int i = 0; i < count; ++i) {
                    const i64 original_x =
                        swap_coordinates
                            ? local_y[i]
                            : local_x[i];

                    const i64 original_y =
                        swap_coordinates
                            ? local_x[i]
                            : local_y[i];

                    const i64 transformed_x =
                        sign_x > 0
                            ? original_x
                            : -original_x;

                    const i64 transformed_y =
                        sign_y > 0
                            ? original_y
                            : -original_y;

                    sort_key[i] =
                        make_descending_key(
                            transformed_x -
                                transformed_y,
                            transformed_x +
                                transformed_y
                        );

                    sort_index[i] = i;
                }

                int *order = radix_sort_keys(
                    count,
                    sort_index,
                    sort_temporary
                );

                ++fenwick_epoch;

                if (fenwick_epoch == 0x7fffffff) {
                    memset(
                        fenwick_stamp,
                        0,
                        sizeof(int) *
                            (size_t)(capacity + 1)
                    );

                    fenwick_epoch = 1;
                }

                const int unique_count =
                    swap_coordinates
                        ? unique_x
                        : unique_y;

                int *base_rank =
                    swap_coordinates
                        ? rank_x
                        : rank_y;

                for (int position = 0;
                     position < count;
                     ++position) {

                    const int point = order[position];

                    int rank = base_rank[point];

                    if (sign_y < 0) {
                        rank =
                            unique_count -
                            1 -
                            rank;
                    }

                    const int reversed_rank =
                        unique_count - rank;

                    i64 best_value = INT64_MAX;
                    int best_point = -1;

                    for (
                        int index = reversed_rank;
                        index > 0;
                        index -= index & -index
                    ) {
                        if (
                            fenwick_stamp[index] ==
                                fenwick_epoch &&
                            fenwick_value[index] <
                                best_value
                        ) {
                            best_value =
                                fenwick_value[index];

                            best_point =
                                fenwick_id[index];
                        }
                    }

                    if (best_point >= 0) {
                        candidate_edges[edge_count].distance =
                            manhattan_distance(
                                point,
                                best_point
                            );

                        candidate_edges[edge_count].from =
                            point;

                        candidate_edges[edge_count].to =
                            best_point;

                        ++edge_count;
                    }

                    const i64 original_x =
                        swap_coordinates
                            ? local_y[point]
                            : local_x[point];

                    const i64 original_y =
                        swap_coordinates
                            ? local_x[point]
                            : local_y[point];

                    const i64 transformed_x =
                        sign_x > 0
                            ? original_x
                            : -original_x;

                    const i64 transformed_y =
                        sign_y > 0
                            ? original_y
                            : -original_y;

                    const i64 value =
                        transformed_x +
                        transformed_y;

                    for (
                        int index = reversed_rank;
                        index <= unique_count;
                        index += index & -index
                    ) {
                        if (
                            fenwick_stamp[index] !=
                            fenwick_epoch
                        ) {
                            fenwick_stamp[index] =
                                fenwick_epoch;

                            fenwick_value[index] = value;
                            fenwick_id[index] = point;
                        } else if (
                            value <
                            fenwick_value[index]
                        ) {
                            fenwick_value[index] = value;
                            fenwick_id[index] = point;
                        }
                    }
                }
            }
        }
    }

    return edge_count;
}

/* ============================================================
 * Main
 * ============================================================ */

int main(void) {
    const int test_count = (int)read_i64();

    for (int test = 0;
         test < test_count;
         ++test) {

        const int n = (int)read_i64();

        ensure_capacity(n);

        for (int i = 0; i < n; ++i) {
            point_x[i] = read_i64();
            point_y[i] = read_i64();
            point_radius[i] = read_i64();

            point_u[i] =
                point_x[i] + point_y[i];

            point_v[i] =
                point_x[i] - point_y[i];

            global_parent[i] = -1;
            kd_order[i] = i;
        }

        /*
         * In transformed coordinates:
         *
         * |x1-x2| + |y1-y2| <= r
         *
         * is equivalent to:
         *
         * |u1-u2| <= r and |v1-v2| <= r.
         */
        build_kd_tree(0, n, 0);

        for (int i = 0; i < n; ++i) {
            query_center = i;

            query_min_u =
                point_u[i] - point_radius[i];

            query_max_u =
                point_u[i] + point_radius[i];

            query_min_v =
                point_v[i] - point_radius[i];

            query_max_v =
                point_v[i] + point_radius[i];

            query_kd_tree(0, n);
        }

        /*
         * Group vertices by their mandatory connected
         * component without an unordered_map.
         */
        memset(
            class_count,
            0,
            sizeof(int) * (size_t)n
        );

        for (int i = 0; i < n; ++i) {
            const int root = global_find(i);

            kd_order[i] = root;
            ++class_count[root];
        }

        class_start[0] = 0;

        for (int i = 0; i < n; ++i) {
            class_start[i + 1] =
                class_start[i] +
                class_count[i];

            class_cursor[i] = class_start[i];
        }

        for (int i = 0; i < n; ++i) {
            const int root = kd_order[i];

            class_members[
                class_cursor[root]++
            ] = i;
        }

        i64 total_cost = 0;
        int answer_count = 0;

        /*
         * Find a Manhattan MST independently inside every
         * mandatory connected component.
         */
        for (int root = 0;
             root < n;
             ++root) {

            const int component_size =
                class_count[root];

            if (component_size <= 1) {
                continue;
            }

            const int component_start =
                class_start[root];

            for (int i = 0;
                 i < component_size;
                 ++i) {

                const int global_id =
                    class_members[
                        component_start + i
                    ];

                local_x[i] = point_x[global_id];
                local_y[i] = point_y[global_id];

                local_parent[i] = -1;
            }

            const int candidate_count =
                build_manhattan_candidates(
                    component_size
                );

            Edge *sorted_edges =
                radix_sort_edges(
                    candidate_edges,
                    temporary_edges,
                    candidate_count
                );

            int needed =
                component_size - 1;

            for (int i = 0;
                 i < candidate_count &&
                 needed > 0;
                 ++i) {

                const Edge edge = sorted_edges[i];

                if (!local_union(
                        edge.from,
                        edge.to
                    )) {
                    continue;
                }

                total_cost += edge.distance;

                answer_from[answer_count] =
                    class_members[
                        component_start +
                        edge.from
                    ] + 1;

                answer_to[answer_count] =
                    class_members[
                        component_start +
                        edge.to
                    ] + 1;

                ++answer_count;
                --needed;
            }
        }

        write_u64((u64)total_cost);
        write_char('\n');

        write_int(answer_count);
        write_char('\n');

        for (int i = 0;
             i < answer_count;
             ++i) {

            write_int(answer_from[i]);
            write_char(' ');
            write_int(answer_to[i]);
            write_char('\n');
        }
    }

    flush_output();
    return 0;
}

Компиляция:

bash
gcc -O2 -pipe -std=c11 solution.c -o solution

Основные улучшения относительно C++-версии:

все рабочие массивы переиспользуются между тестами;
unordered_map заменён группировкой через массивы префиксных сумм;
KD-дерево хранит bounding box каждого поддерева;
если запрос полностью покрывает поддерево, оно обрабатывается линейным проходом без дальнейшей рекурсии;
std::sort и nth_element на этапе Manhattan MST заменены специализированными radix sort;
очистка Fenwick tree выполняется через timestamps, без memset для каждого из восьми проходов;
кандидаты рёбер хранят вес в uint32_t, поскольку Manhattan-расстояние не превосходит 2·10⁹.

Answer 5

Главная проблема текущего решения — чтение всего stdin в память. При большом тесте вход занимает сотни мегабайт. Здесь ввод читается потоковым буфером на 1 МиБ, а память составляет примерно 8·T + 1 МиБ, то есть около 81 МиБ при T = 10⁷.

c
#define _GNU_SOURCE

#include <errno.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/mman.h>

#define INPUT_BUFFER_SIZE (1u << 20)

static unsigned char input_buffer[INPUT_BUFFER_SIZE + 1];

static unsigned char *input_ptr = input_buffer;
static unsigned char *input_end = input_buffer;

/*
 * При достижении настоящего EOF добавляем искусственный
 * разделитель. Это позволяет корректно прочитать последнее
 * число, даже если после него нет перевода строки.
 */
static inline void refill_input(void) {
    ssize_t bytes_read;

    do {
        bytes_read = read(
            STDIN_FILENO,
            input_buffer,
            INPUT_BUFFER_SIZE
        );
    } while (bytes_read < 0 && errno == EINTR);

    if (bytes_read <= 0) {
        input_buffer[0] = '\n';
        input_ptr = input_buffer;
        input_end = input_buffer + 1;
        return;
    }

    input_ptr = input_buffer;
    input_end = input_buffer + bytes_read;
}

static inline uint32_t read_u32(void) {
    unsigned int digit;
    uint32_t value;

    /*
     * Пропускаем пробелы и переводы строк.
     */
    for (;;) {
        if (__builtin_expect(input_ptr == input_end, 0)) {
            refill_input();
        }

        digit = (unsigned int)(*input_ptr++ - '0');

        if (digit < 10u) {
            break;
        }
    }

    value = (uint32_t)digit;

    /*
     * Читаем остальные цифры.
     */
    for (;;) {
        if (__builtin_expect(input_ptr == input_end, 0)) {
            refill_input();
        }

        digit = (unsigned int)(*input_ptr - '0');

        if (digit >= 10u) {
            ++input_ptr;
            return value;
        }

        ++input_ptr;
        value = value * 10u + (uint32_t)digit;
    }
}

int main(void) {
    const uint32_t request_count = read_u32();
    const uint32_t time_limit = read_u32();

    /*
     * Индексы нужны только от 0 до T-1.
     *
     * Если f == T, изменение diff[T] записывать не требуется:
     * после момента T пиковую нагрузку считать уже не нужно.
     */
    const size_t diff_bytes =
        (size_t)time_limit * sizeof(int64_t);

    int used_mmap = 1;

    int64_t *diff = mmap(
        NULL,
        diff_bytes,
        PROT_READ | PROT_WRITE,
        MAP_PRIVATE | MAP_ANONYMOUS,
        -1,
        0
    );

    if (diff == MAP_FAILED) {
        used_mmap = 0;

        diff = calloc(
            (size_t)time_limit,
            sizeof(*diff)
        );

        if (diff == NULL) {
            return 0;
        }
    } else {
#ifdef MADV_HUGEPAGE
        /*
         * Может уменьшить число TLB-промахов при случайных
         * обновлениях большого массива.
         */
        (void)madvise(
            diff,
            diff_bytes,
            MADV_HUGEPAGE
        );
#endif
    }

    uint32_t first_used_time = time_limit;
    uint32_t last_finish_time = 0;

    for (uint32_t i = 0; i < request_count; ++i) {
        const uint32_t start = read_u32();
        const uint32_t finish = read_u32();
        const int64_t amount = (int64_t)read_u32();

        diff[start] += amount;

        /*
         * Для полуинтервала [start, finish) велосипеды
         * освобождаются непосредственно в момент finish.
         */
        if (finish < time_limit) {
            diff[finish] -= amount;
        }

        if (start < first_used_time) {
            first_used_time = start;
        }

        if (finish > last_finish_time) {
            last_finish_time = finish;
        }
    }

#ifdef MADV_SEQUENTIAL
    if (used_mmap) {
        (void)madvise(
            diff +
                first_used_time,
            (size_t)(
                last_finish_time -
                first_used_time
            ) * sizeof(*diff),
            MADV_SEQUENTIAL
        );
    }
#endif

    int64_t current = 0;
    int64_t maximum = 0;

    /*
     * Сканируем только диапазон, в котором могли быть
     * активные заявки, а не обязательно все 0..T.
     */
    const int64_t *position =
        diff + first_used_time;

    const int64_t *end =
        diff + last_finish_time;

    while (position < end) {
        current += *position++;

        if (current > maximum) {
            maximum = current;
        }
    }

    printf("%lld\n", (long long)maximum);

    if (used_mmap) {
        munmap(diff, diff_bytes);
    } else {
        free(diff);
    }

    return 0;
}

Компиляция:

bash
gcc -O3 -pipe -std=gnu11 solution.c -o solution

Сложность:

время: O(N + L), где L — длина диапазона от минимального a до максимального f;
память: 8·T + O(1) байт;
при T = 10⁷ массив занимает примерно 76,3 МиБ, вместо хранения ещё и всего входного файла.

Answer 6

Ниже — оптимизированная реализация на C17. Она повторяет эффективную идею исходного C++-решения:

фотографии хранятся в splay-дереве в порядке слева направо;
после каждой фотографии хранится длина свободного промежутка;
в поддереве хранится максимальный промежуток для поиска самого левого подходящего места;
уплотнение выполняется лениво за O(log N), а не полным проходом;
узел фотографии напрямую определяется по номеру команды ADD;
все узлы размещены в одном массиве, без отдельных malloc.

c
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

#define INPUT_BUFFER_SIZE  (1u << 20)
#define OUTPUT_BUFFER_SIZE (1u << 20)

#define LAZY_ZERO  0x80000000u
#define PARENT_MASK 0x7fffffffu

typedef struct {
    uint32_t left;
    uint32_t right;

    /*
     * Младшие 31 бит — номер родителя.
     * Старший бит — ленивое обнуление всех gap в поддереве.
     */
    uint32_t parent_and_flag;

    uint32_t width;
    uint32_t gap_after;
    uint32_t max_gap;
} Node;

/* ============================================================
 * Fast input
 * ============================================================ */

static unsigned char input_buffer[INPUT_BUFFER_SIZE];
static size_t input_position = 0;
static size_t input_length = 0;

static inline int next_byte(void) {
    if (__builtin_expect(input_position == input_length, 0)) {
        input_length = fread(
            input_buffer,
            1,
            sizeof(input_buffer),
            stdin
        );

        input_position = 0;

        if (input_length == 0) {
            return EOF;
        }
    }

    return input_buffer[input_position++];
}

static inline uint32_t read_uint(void) {
    int c;

    do {
        c = next_byte();
    } while (c < '0' || c > '9');

    uint32_t value = 0;

    do {
        value =
            value * 10u +
            (uint32_t)(c - '0');

        c = next_byte();
    } while (c >= '0' && c <= '9');

    return value;
}

static inline int read_operation(void) {
    int c;

    do {
        c = next_byte();
    } while (c != 'A' && c != 'D');

    const int operation = c;

    /*
     * Пропускаем остаток ADD или DEL.
     */
    do {
        c = next_byte();
    } while (c > ' ');

    return operation;
}

/* ============================================================
 * Fast output
 * ============================================================ */

static char output_buffer[OUTPUT_BUFFER_SIZE];
static size_t output_position = 0;

static inline void flush_output(void) {
    if (output_position != 0) {
        fwrite(
            output_buffer,
            1,
            output_position,
            stdout
        );

        output_position = 0;
    }
}

static inline void reserve_output(size_t required) {
    if (output_position + required > OUTPUT_BUFFER_SIZE) {
        flush_output();
    }
}

static inline void write_uint(uint32_t value) {
    char digits[16];
    int count = 0;

    do {
        digits[count++] =
            (char)('0' + value % 10u);

        value /= 10u;
    } while (value != 0);

    while (count != 0) {
        output_buffer[output_position++] =
            digits[--count];
    }
}

static inline void write_pair(
    uint32_t coordinate,
    uint32_t width
) {
    reserve_output(32);

    write_uint(coordinate);
    output_buffer[output_position++] = ' ';
    write_uint(width);
    output_buffer[output_position++] = '\n';
}

static inline void write_overflow(void) {
    static const char text[] = "OVERFLOW\n";

    reserve_output(sizeof(text) - 1);

    for (size_t i = 0; i + 1 < sizeof(text); ++i) {
        output_buffer[output_position++] = text[i];
    }
}

/* ============================================================
 * Shelf / splay tree
 * ============================================================ */

typedef struct {
    Node *nodes;

    /*
     * Используется для раскрытия lazy-операций на пути
     * от корня к произвольному узлу и для inorder-обхода.
     */
    uint32_t *stack;

    uint32_t root;
    uint32_t total_free;
} Shelf;

static inline uint32_t node_parent(
    const Shelf *shelf,
    uint32_t node
) {
    return
        shelf->nodes[node].parent_and_flag &
        PARENT_MASK;
}

static inline int node_has_lazy_zero(
    const Shelf *shelf,
    uint32_t node
) {
    return
        (
            shelf->nodes[node].parent_and_flag &
            LAZY_ZERO
        ) != 0;
}

static inline void set_parent(
    Shelf *shelf,
    uint32_t node,
    uint32_t parent
) {
    if (node == 0) {
        return;
    }

    shelf->nodes[node].parent_and_flag =
        (
            shelf->nodes[node].parent_and_flag &
            LAZY_ZERO
        ) |
        parent;
}

/*
 * Лениво обнулить все внутренние промежутки поддерева.
 */
static inline void apply_zero(
    Shelf *shelf,
    uint32_t node
) {
    if (node == 0) {
        return;
    }

    Node *current = &shelf->nodes[node];

    current->gap_after = 0;
    current->max_gap = 0;
    current->parent_and_flag |= LAZY_ZERO;
}

static inline void push(
    Shelf *shelf,
    uint32_t node
) {
    Node *current = &shelf->nodes[node];

    if (!node_has_lazy_zero(shelf, node)) {
        return;
    }

    apply_zero(shelf, current->left);
    apply_zero(shelf, current->right);

    current->parent_and_flag &= PARENT_MASK;
}

static inline void pull(
    Shelf *shelf,
    uint32_t node
) {
    Node *current = &shelf->nodes[node];

    uint32_t maximum = current->gap_after;

    const uint32_t left_max =
        shelf->nodes[current->left].max_gap;

    const uint32_t right_max =
        shelf->nodes[current->right].max_gap;

    if (left_max > maximum) {
        maximum = left_max;
    }

    if (right_max > maximum) {
        maximum = right_max;
    }

    current->max_gap = maximum;
}

static inline void rotate(
    Shelf *shelf,
    uint32_t node
) {
    Node *nodes = shelf->nodes;

    const uint32_t parent = node_parent(shelf, node);
    const uint32_t grandparent =
        node_parent(shelf, parent);

    const int is_right_child =
        nodes[parent].right == node;

    uint32_t middle;

    if (is_right_child) {
        middle = nodes[node].left;

        nodes[parent].right = middle;
        nodes[node].left = parent;
    } else {
        middle = nodes[node].right;

        nodes[parent].left = middle;
        nodes[node].right = parent;
    }

    set_parent(shelf, middle, parent);
    set_parent(shelf, parent, node);
    set_parent(shelf, node, grandparent);

    if (grandparent == 0) {
        shelf->root = node;
    } else if (nodes[grandparent].left == parent) {
        nodes[grandparent].left = node;
    } else {
        nodes[grandparent].right = node;
    }

    pull(shelf, parent);
    pull(shelf, node);
}

/*
 * Все lazy-операции на пути root -> node уже должны
 * быть раскрыты.
 */
static inline void splay_pushed(
    Shelf *shelf,
    uint32_t node
) {
    Node *nodes = shelf->nodes;

    while (node_parent(shelf, node) != 0) {
        const uint32_t parent =
            node_parent(shelf, node);

        const uint32_t grandparent =
            node_parent(shelf, parent);

        if (grandparent != 0) {
            const int node_is_left =
                nodes[parent].left == node;

            const int parent_is_left =
                nodes[grandparent].left == parent;

            if (node_is_left == parent_is_left) {
                rotate(shelf, parent);
            } else {
                rotate(shelf, node);
            }
        }

        rotate(shelf, node);
    }
}

/*
 * Узел найден напрямую по номеру команды. Перед splay
 * необходимо раскрыть lazy-операции сверху вниз.
 */
static inline void push_path_and_splay(
    Shelf *shelf,
    uint32_t node
) {
    uint32_t count = 0;
    uint32_t current = node;

    while (current != 0) {
        shelf->stack[count++] = current;
        current = node_parent(shelf, current);
    }

    while (count != 0) {
        push(shelf, shelf->stack[--count]);
    }

    splay_pushed(shelf, node);
}

/*
 * Найти самый левый промежуток длины не меньше width.
 * Гарантируется, что такой промежуток существует.
 *
 * Возвращается фотография, непосредственно после которой
 * расположен найденный промежуток.
 */
static uint32_t find_leftmost_fit(
    Shelf *shelf,
    uint32_t width
) {
    Node *nodes = shelf->nodes;
    uint32_t node = shelf->root;

    for (;;) {
        push(shelf, node);

        const uint32_t left = nodes[node].left;

        if (nodes[left].max_gap >= width) {
            node = left;
            continue;
        }

        if (nodes[node].gap_after >= width) {
            splay_pushed(shelf, node);
            return node;
        }

        node = nodes[node].right;
    }
}

/*
 * Собрать всё свободное место справа.
 *
 * Обнуление промежутков во всём дереве выполняется лениво,
 * поэтому полного прохода по фотографиям нет.
 */
static void compact_shelf(Shelf *shelf) {
    Node *nodes = shelf->nodes;

    apply_zero(shelf, shelf->root);

    uint32_t last = shelf->root;

    for (;;) {
        push(shelf, last);

        if (nodes[last].right == 0) {
            break;
        }

        last = nodes[last].right;
    }

    splay_pushed(shelf, last);

    nodes[last].gap_after = shelf->total_free;
    pull(shelf, last);
}

/*
 * Корень — фотография, после которой вставляется новая.
 */
static inline void insert_after_root(
    Shelf *shelf,
    uint32_t node_id,
    uint32_t width
) {
    Node *nodes = shelf->nodes;

    const uint32_t root = shelf->root;
    const uint32_t old_gap = nodes[root].gap_after;
    const uint32_t old_right = nodes[root].right;

    Node *new_node = &nodes[node_id];

    new_node->left = 0;
    new_node->right = old_right;
    new_node->parent_and_flag = root;

    new_node->width = width;
    new_node->gap_after = old_gap - width;
    new_node->max_gap = old_gap - width;

    set_parent(shelf, old_right, node_id);

    nodes[root].right = node_id;
    nodes[root].gap_after = 0;

    pull(shelf, node_id);
    pull(shelf, root);
}

static int shelf_add(
    Shelf *shelf,
    uint32_t width,
    uint32_t action_id
) {
    Node *nodes = shelf->nodes;

    if (width > shelf->total_free) {
        return 0;
    }

    if (nodes[shelf->root].max_gap >= width) {
        find_leftmost_fit(shelf, width);
    } else {
        /*
         * Суммарного места достаточно, но ни один
         * непрерывный промежуток не подходит.
         */
        compact_shelf(shelf);
    }

    /*
     * Узел 1 — фиктивная фотография.
     * Команде action_id соответствует action_id + 1.
     */
    insert_after_root(
        shelf,
        action_id + 1u,
        width
    );

    shelf->total_free -= width;

    return 1;
}

static void shelf_delete(
    Shelf *shelf,
    uint32_t add_action_id
) {
    Node *nodes = shelf->nodes;

    const uint32_t victim =
        add_action_id + 1u;

    push_path_and_splay(shelf, victim);

    const uint32_t left_root =
        nodes[victim].left;

    const uint32_t right_root =
        nodes[victim].right;

    /*
     * Свободный промежуток после предыдущей фотографии
     * увеличивается на ширину удаляемой фотографии и на
     * уже существовавший промежуток после неё.
     */
    const uint32_t released =
        nodes[victim].width +
        nodes[victim].gap_after;

    shelf->total_free += nodes[victim].width;

    set_parent(shelf, left_root, 0);
    set_parent(shelf, right_root, 0);

    /*
     * В левой части всегда есть фиктивный узел.
     */
    shelf->root = left_root;

    uint32_t predecessor = left_root;

    for (;;) {
        push(shelf, predecessor);

        if (nodes[predecessor].right == 0) {
            break;
        }

        predecessor = nodes[predecessor].right;
    }

    splay_pushed(shelf, predecessor);

    /*
     * predecessor теперь является корнем левой части.
     */
    nodes[predecessor].gap_after += released;
    nodes[predecessor].right = right_root;

    set_parent(shelf, right_root, predecessor);

    pull(shelf, predecessor);
}

static void shelf_print(Shelf *shelf) {
    Node *nodes = shelf->nodes;

    uint32_t stack_size = 0;
    uint32_t current = shelf->root;
    uint32_t coordinate = 0;

    /*
     * Итеративный inorder-обход.
     */
    while (current != 0 || stack_size != 0) {
        while (current != 0) {
            push(shelf, current);

            shelf->stack[stack_size++] = current;
            current = nodes[current].left;
        }

        current = shelf->stack[--stack_size];

        /*
         * Узел 1 — фиктивная фотография перед полкой.
         */
        if (current != 1) {
            write_pair(
                coordinate,
                nodes[current].width
            );
        }

        coordinate +=
            nodes[current].width +
            nodes[current].gap_after;

        current = nodes[current].right;
    }
}

/* ============================================================
 * Main
 * ============================================================ */

int main(void) {
    const uint32_t shelf_length = read_uint();
    const uint32_t action_count = read_uint();

    const size_t node_count =
        (size_t)action_count + 2u;

    Shelf shelf;

    /*
     * calloc сразу создаёт нулевой null-узел с номером 0
     * и не требует отдельной инициализации каждого узла.
     */
    shelf.nodes = calloc(
        node_count,
        sizeof(*shelf.nodes)
    );

    shelf.stack = malloc(
        node_count * sizeof(*shelf.stack)
    );

    if (shelf.nodes == NULL || shelf.stack == NULL) {
        free(shelf.nodes);
        free(shelf.stack);
        return 0;
    }

    /*
     * Узел 1 — фиктивная фотография нулевой ширины,
     * стоящая перед началом полки.
     *
     * Свободное место перед первой реальной фотографией
     * представлено как gap_after фиктивного узла.
     */
    shelf.root = 1;
    shelf.total_free = shelf_length;

    shelf.nodes[1].gap_after = shelf_length;
    shelf.nodes[1].max_gap = shelf_length;

    for (
        uint32_t action_id = 1;
        action_id <= action_count;
        ++action_id
    ) {
        const int operation = read_operation();
        const uint32_t argument = read_uint();

        if (operation == 'A') {
            if (!shelf_add(
                    &shelf,
                    argument,
                    action_id
                )) {
                write_overflow();
                shelf_print(&shelf);
                flush_output();

                free(shelf.stack);
                free(shelf.nodes);

                return 0;
            }
        } else {
            shelf_delete(&shelf, argument);
        }
    }

    shelf_print(&shelf);
    flush_output();

    free(shelf.stack);
    free(shelf.nodes);

    return 0;
}

Компиляция:

bash
gcc -O3 -pipe -std=c17 solution.c -o solution

Сложность

Амортизированно:

ADD: O(log N);
DEL: O(log N);
уплотнение: O(log N), без обхода всех фотографий;
финальный вывод: O(P), где P — число оставшихся фотографий.

Общая сложность — O(N log N + P), память — около:

24 · (N + 2) байт на узлы;
4 · (N + 2) байт на стек.

При N = 3·10⁶ это примерно 80 МиБ, не считая небольших буферов ввода и вывода.

Кодерун планирует идеальный летний день в парке ...

質問

思考

回答

Что изменилось

質問

思考

回答

質問

思考

回答

Optimizations applied

質問

思考

回答

質問

思考

回答

質問

思考

回答

Сложность

このQ&Aを共有