Submission #711280

#	Time	Username	Problem	Language	Result	Execution time	Memory
711280		_martynas	Swimming competition (LMIO18_plaukimo_varzybos)	C++11	100 / 100	570 ms	99280 KiB

plaukimo_varzybos

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;

#define F first
#define S second
#define PB push_back

void FASTIO() {ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); }

const int MXN = 1e6+5;

int n, a, b;
int T[MXN];
int dp[MXN];
multiset<int> MS1;
multiset<int> MS2;
vector<int> event[2*MXN];
bool moved[2*MXN];

int main() {
    FASTIO();
    cin >> n >> a >> b;
    for(int i = 1; i <= n; i++) {
        cin >> T[i];
    }
    sort(T+1, T+n+1);
    fill(dp, dp+n+1, MXN);

    dp[0] = 0;
    int j = 0;
    for(int i = 1; i <= n; i++) {
        for(; j <= T[i]; j++) {
            //cerr << "j = " << j << "\n";
            while(!event[j].empty()) {
                int x = event[j].back();
                if(moved[x]) {
                    event[j].pop_back();
                    continue;
                }
                moved[x] = true;
                MS1.erase(MS1.find(dp[x]));
                MS2.insert(T[x+1]);
                event[j].pop_back();
            }
        } j--;
        int l = i-b, r = i-a;
        if(r < 0) continue;
        if(l-1 >= 0) {
            if(!moved[l-1]) MS1.erase(MS1.find(dp[l-1]));
            else MS2.erase(MS2.find(T[l]));
            moved[l-1] = true;
        }
        if(T[r+1]+dp[r] > T[i]) {
            MS1.insert(dp[r]);
            event[T[r+1]+dp[r]].PB(r);
        }
        else {
            moved[r] = true;
            MS2.insert(T[r+1]);
        }
        if(!MS1.empty()) dp[i] = min(dp[i], *MS1.begin());
        if(!MS2.empty()) dp[i] = min(dp[i], T[i]-(*MS2.rbegin()));
    }
    cout << dp[n] << "\n";

    return 0;
}

/*



*/

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40