Submission #46289

#	Time	Username	Problem	Language	Result	Execution time	Memory
46289		qoo2p5	Sparklers (JOI17_sparklers)	C++17	0 / 100	3 ms	560 KiB

sparklers

    #include <bits/stdc++.h>
     
    using namespace std;
     
    typedef long long ll;
     
    const int INF = (int) 1e9 + 1e6 + 123;
    const ll LINF = (ll) 1e18 + 1e9 + 123;
     
    #define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
    #define per(i, s, t) for (auto i = (s); i >= (t); --(i))
    #define sz(x) ((int)(x).size())
    #define mp make_pair
    #define pb push_back
    #define all(x) (x).begin(), (x).end()
     
    bool mini(auto &x, const auto &y) {
        if (y < x) {
            x = y;
            return 1;
        }
        return 0;
    }
     
    bool maxi(auto &x, const auto &y) {
        if (y > x) {
            x = y;
            return 1;
        }
        return 0;
    }
     
    void run();
     
    int main() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        run();
        return 0;
    }
     
    const int N = (int) 1e5 + 123;
     
    ll t;
     
    ll calc_need(ll c, vector<ll> people, ll bonus=0) {
        if (sz(people) == 0) {
            return 0;
        }
        
        ll left = -1;
        for (ll &x : people) {
            x = max(0LL, x - bonus);
        }
        ll right = people[0];
        
        while (right - left > 1) {
            ll mid = (left + right) / 2;
            ll have_time = mid;
            vector<ll> tmp = people;
            ll sum = 0;
            while (sz(tmp)) {
                if (sum + have_time >= tmp.back() - sum - have_time) {
                    sum += have_time;
                    have_time = 2 * t * c;
                    tmp.pop_back();
                } else {
                    break;
                }
            }
            if (sz(tmp)) {
                left = mid;
            } else {
                right = mid;
            }
        }
        
        return right;
    }
     
    bool check(vector<ll> x, int k, ll c, ll bonus=0) {
        int n = sz(x);
        vector<ll> right_people;
        per(i, n - 1, k + 1) {
            right_people.push_back((x[i] - x[k]) * 2);
        }
        ll need_right = calc_need(c, right_people, bonus);
        
        vector<ll> left_people;
        rep(i, 0, k) {
            left_people.push_back((x[k] - x[i]) * 2);
        }
        ll need_left = calc_need(c, left_people, bonus);
        
        return need_left + need_right <= 2 * t * c;
    }
     
    bool wow(vector<ll> x, int k, ll c) {
        if (check(x, k, c)) {
            return true;
        }
        
        if (k == 0) {
            return false;
        }
        
        ll to = x[k] - t * c;
        if (x[k - 1] + t * c < to) {
            return false;
        }
            
        {
            ll bonus = 2 * t * c - (x[k] - x[k - 1]);
            
            vector<ll> w = x;
            for (ll &it : w) {
                it *= 2;
            }
            
            ll moved = x[k] - x[k - 1];
            int tk = k - 1;
            w[tk] = max(0LL, w[tk] + moved);
            w.erase(w.begin() + k);
            per(i, tk - 1, 0) {
                w[i] += moved;
                w[i] = min(w[i], w[i + 1]);
            }
            rep(i, tk + 1, sz(w)) {
                w[i] -= moved;
                w[i] = max(w[i], w[i - 1]);
            }
            
            vector<ll> right_people;
            per(i, sz(w) - 1, tk + 1) {
                right_people.push_back(w[i] - w[tk]);
            }
            ll need_right = calc_need(c, right_people, 0);
            
            vector<ll> left_people;
            rep(i, 0, k) {
                left_people.push_back(w[tk] - w[i]);
            }
            ll need_left = calc_need(c, left_people, 0);
            
            if (need_left + need_right <= 2 * t * c + bonus) {
                return true;
            }
        }
        
        x.erase(x.begin() + k);
        k--;
        x[k] = max(0LL, to);
        per(i, k - 1, 0) {
            x[i] += t * c;
            x[i] = min(x[i], x[i + 1]);
        }
        rep(i, k + 1, sz(x)) {
            x[i] -= t * c;
            x[i] = max(x[i], x[i - 1]);
        }
        
        return wow(x, k, c);
    }
     
    void run() {
        int n, k;
        cin >> n >> k >> t;
        k--;
        vector<ll> x(n);
        rep(i, 0, n) {
            cin >> x[i];
        }
        
        ll result = LINF;
        
        rep(iter, 0, 2) {
            ll left = 0;
            ll right = (x[n - 1] / t) + 1;
            while (right - left > 1) {
                ll mid = (left + right) / 2;
                if (wow(x, k, mid)) {
                    right = mid;
                } else {
                    left = mid;
                }
            }
            
            mini(result, right);
            
            k = n - 1 - k;
            vector<ll> tmp(n);
            rep(i, 0, n) {
                tmp[i] = x[n - 1] - x[i];
            }
            reverse(all(tmp));
            rep(i, 0, n) {
                x[i] = tmp[i];
            }
        }
        
        cout << result << "\n";
    }

• Subtask 1: 0 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 50