Submission #1165428

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165428		BlockOG	Holiday (IOI14_holiday)	C++20	0 / 100	11 ms	1552 KiB

holiday

#include "holiday.h"
#include <algorithm>
#include <iostream>
#include <utility>

// meow mrrow nya nya :3c
// play vivid/stasis. free on steam

using namespace std;

pair<int, int> sacl[100000];
pair<int, int> sacr[100000];

long long findMaxAttraction(int n, int start, int d, int attraction[]) {
    for (int i = 0; i < start; i++) sacl[i] = {attraction[i], start - i + 1};
    sort(sacl, sacl + start, [](pair<int, int> a, pair<int, int> b) { return a.first * b.second > b.first * a.second; });

    for (int i = 0; i < n - start; i++) sacr[i] = {attraction[start + i], i + 1};
    sort(sacr, sacr + n - start, [](pair<int, int> a, pair<int, int> b) { return a.first * b.second > b.first * a.second; });

    // for (int i = 0; i < start; i++) cout << sacl[i].first << '/' << sacl[i].second << ' ';
    // cout << endl;
    // for (int i = 0; i < n - start; i++) cout << sacr[i].first << '/' << sacr[i].second << ' ';
    // cout << endl;

    int furthestl = 0;
    int furthestr = 0;
    int selected = 0;
    bool anyl = false;
    bool anyr = false;

#define FURTHESTL (anyl ? furthestl : -furthestr)
#define FURTHESTR (anyr ? furthestr : -furthestl)

    long long res = 0;
    for (int i = 0, j = 0; i < n - start || j < start;) {
        bool done_other = false;
        if (j >= start ||
            i < n - start && sacr[i].first * max(1, sacl[j].second - FURTHESTL) > sacl[j].first * max(1, sacr[i].second - FURTHESTR)) {
            if (false) {
            r:
                if (done_other) break;
                done_other = true;
            }

            int nfurthestr = max(furthestr, sacr[i].second - 1);
            if (furthestl + nfurthestr + min(furthestl, nfurthestr) + selected + 1 <= d) {
                furthestr = nfurthestr;
                selected++;
                res += sacr[i++].first;
                anyr = true;
            } else goto l;
        } else {
            if (false) {
            l:
                if (done_other) break;
                done_other = true;
            }

            int nfurthestl = max(furthestl, sacl[j].second - 1);
            if (nfurthestl + furthestr + min(nfurthestl, furthestr) + selected + 1 <= d) {
                furthestl = nfurthestl;
                selected++;
                res += sacl[j++].first;
                anyl = true;
            } else goto r;
        }
    }

    return res;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 23
• Subtask 3: 0 / 17
• Subtask 4: 0 / 53