oj.uz

Submission #45628

# Submission time Handle Problem Language Result Execution time Memory
45628 2018-04-15T16:48:12 Z qoo2p5 Sparklers (JOI17_sparklers) C++17
0 / 100
 4 ms 668 KB 
#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 = 2 * x[n - 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.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 496 KB Output is correct
3 Correct 2 ms 496 KB Output is correct
4 Correct 3 ms 496 KB Output is correct
5 Correct 4 ms 496 KB Output is correct
6 Correct 2 ms 668 KB Output is correct
7 Incorrect 2 ms 668 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 496 KB Output is correct
3 Correct 2 ms 496 KB Output is correct
4 Correct 3 ms 496 KB Output is correct
5 Correct 4 ms 496 KB Output is correct
6 Correct 2 ms 668 KB Output is correct
7 Incorrect 2 ms 668 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 496 KB Output is correct
3 Correct 2 ms 496 KB Output is correct
4 Correct 3 ms 496 KB Output is correct
5 Correct 4 ms 496 KB Output is correct
6 Correct 2 ms 668 KB Output is correct
7 Incorrect 2 ms 668 KB Output isn't correct
8 Halted 0 ms 0 KB -