Submission #773576

#	Time	Username	Problem	Language	Result	Execution time	Memory
773576		phoebe	Holiday (IOI14_holiday)	C++17	23 / 100	5063 ms	6060 KiB

holiday

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

#define ll long long
#define pii pair<int, int>
#define F first
#define S second
#define FOR(i, n) for (int i = 0; i < n; i++)
const int INF = 1e9 + 7;

const int maxn = 1e5 + 10;
int n, s, d, a[maxn];

int calc_dist(int l, int r){
    if (l >= s) return r - s;
    if (r <= s) return s - l;
    return r - l + min(r - s, s - l);
}

ll solve(int l){
    // cout << "kore wa beginning" << endl;
    // cout << n << ' ' << ' ' << s << ' ' << d << endl;
    set<pii> include, removed; ll best = 0, include_sum = 0;
    for (int i = l; i <= s; i++){
        removed.insert({a[i], i});
    }
    for (int r = s + 1; r < n; r++){
        if (calc_dist(l, r) > d) break;
        // cout << l << ' ' << r << endl;
        removed.insert({a[r], r});
        // while (calc_dist(l, r) > d){
        //     if (include.count({a[l], l})){
        //         include.erase({a[l], l});
        //         include_sum -= a[l];
        //     }
        //     else removed.erase({a[l], l});
        //     l++;
        // }
        // rebalance
        while (include.size() > 0 && removed.size() > 0 &&
        include.begin()->F < removed.rbegin()->F){
            pii x = *include.begin(), y = *removed.rbegin();
            include_sum -= x.F; include.erase(x);
            removed.erase(y);
            include_sum += y.F; include.insert(y);
            removed.insert(x);
        }
        // adding elements if we can
        int can_include = d - calc_dist(l, r);
        while (include.size() < can_include && removed.size() > 0){
            pii x = *removed.rbegin(); removed.erase(x);
            include_sum += x.F; include.insert(x);
        }
        // removing elements if we must
        while (include.size() > can_include){
            pii x = *include.begin(); include.erase(x);
            include_sum -= x.F; removed.insert(x);
        }
        // while (l < s){
        //     int can_include = d - calc_dist(l, r);
        //     int can_include_prime = d - calc_dist(l + 1, r);
        //     ll delta = 0;
        //     if (include.count({a[l], l})){
        //         delta -= a[l];
        //         can_include_prime++;
        //     }
        //     else{
        //         removed.erase({a[l], l});
        //     }
        //     auto it = removed.rbegin();
        //     vector<pii> to_remove;
        //     FOR(_, min((int)removed.size(), can_include_prime - can_include)){
        //         to_remove.push_back(*it);
        //         delta += it->F; it++;
        //     }
        //     if (delta < 0 && include.count({a[l], l})) break;
        //     if (include.count({a[l], l})){
        //         include.erase({a[l], l});
        //     }
        //     for (auto x : to_remove){
        //         removed.erase(x);
        //         include.insert(x);
        //     }
        //     include_sum += delta; l++;
        // }
        // cout << l << ' ' << r << endl;
        // if (l == 27 && r == 588) cout << include_sum << endl;
        // assert(!(l == 27 && r == 588));
        best = max(best, include_sum);
    }
    return best;
}

ll heh(int l, int r){
    int can_include = d - calc_dist(l, r);
    priority_queue<int> pq;
    for (int i = l; i <= r; i++) pq.push(a[i]);
    ll sum = 0;
    while (!pq.empty() && can_include > 0){
        sum += pq.top(); pq.pop();
        can_include--;
    }
    return sum;
}

ll findMaxAttraction(int N, int start, int D, int attraction[]){
    n = N, s = start, d = D;
    for (int i = 0; i < n; i++) a[i] = attraction[i];
    // ll best = 0; int best_l, best_r;
    // for (int l = 0; l < n; l++){
    //     for (int r = l; r < n; r++){
    //         ll ans = heh(l, r);
    //         if (ans > best) best = ans, best_l = l, best_r = r; 
    //     }
    // }
    // cout << best_l << ' ' << best_r << endl;
    // return best;
    ll re = 0;
    for (int l = 0; l <= s; l++){
        re = max(re, solve(l));
    }
    return re;
    // ll re = solve();
    // reverse(a, a + n); s = n - 1 - start;
    // re = max(re, solve());
    // return re;
}

Compilation message (stderr)

holiday.cpp: In function 'long long int solve(int)':
holiday.cpp:51:31: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   51 |         while (include.size() < can_include && removed.size() > 0){
      |                ~~~~~~~~~~~~~~~^~~~~~~~~~~~~
holiday.cpp:56:31: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   56 |         while (include.size() > can_include){
      |                ~~~~~~~~~~~~~~~^~~~~~~~~~~~~

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