Submission #772909

#	Time	Username	Problem	Language	Result	Execution time	Memory
772909		phoebe	Holiday (IOI14_holiday)	C++17	30 / 100	73 ms	5892 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(){
    // cout << "kore wa beginning" << endl;
    // cout << n << ' ' << ' ' << s << ' ' << d << endl;
    set<pii> include, removed; ll best = 0, include_sum = 0;
    for (int i = 0; i < s; i++){
        removed.insert({a[i], i});
    }
    int l = 0;
    for (int r = s; r < min(s + d, n); r++){
        // 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);
        }
        // cout << "asd " << include.size() << ' ' << calc_dist(l, r) << ' ' << d << endl;
        while (l < s){
            // cout << l << ' ' << r << ' ' << include_sum << endl;
            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});
            }
            // cout << 'd';
            // cout << can_include_prime - can_include << endl;
            // cout << 'c';
            auto it = removed.rbegin();
            vector<pii> to_remove;
            // cout << 'b';
            FOR(_, min((int)removed.size(), can_include_prime - can_include)){
                to_remove.push_back(*it);
                delta += it->F; it++;
            }
            // cout << delta << ' ' << a[s] << endl;
            // cout << 'a';
            if (delta < 0){
                if (include.count({a[l], l}) == 0){
                    removed.insert({a[l], l});
                }
                break;
            }
            // cout << "absdjk";
            // cout << delta << ' ' << a[s] << endl;
            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 << delta << ' ' << a[s] << endl;
        }
        assert(l <= s);
        // cout << l << ' ' << r << ' ' << include_sum << endl;
        best = max(best, include_sum);
    }
    // cout << best << endl;
    return best;
}

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 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()':
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: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 0 / 17
• Subtask 4: 0 / 53