Submission #66846

#	Time	Username	Problem	Language	Result	Execution time	Memory
66846		elitewantsyou	Sparklers (JOI17_sparklers)	C++14	0 / 100	2 ms	376 KiB

sparklers

#include <bits/stdc++.h>

#define fi first
#define se second
#define fin(s) freopen( s, "r", stdin );
#define fout(s) freopen( s, "w", stdout );

const long long N = 100100;
const long long Q = N * 30;
const long long mod = 1e9 + 7;
const long long MAGIC = 30;

using namespace std;

int n;
int k;
int t;
int a[N];

bool can(long long s)
{
        s *= t;
        vector < long long > l, r;
        for(int i = 1; i < k; i++){
                l.push_back(a[k] - a[i]);
        }
        for(int i = n; i > k; i--){
                r.push_back(a[i] - a[k]);
        }
        /*for(int x: l){
                cout << x << " ";
        } cout << "\n";
        for(int i = 0; i + 1 < l.size(); i++){
                cout << l[i] - l[i + 1] << " ";
        } cout << "\n";
        for(int x: r){
                cout << x << " ";
        } cout << "\n";
        for(int i = 0; i + 1 < r.size(); i++){
                cout << r[i] - r[i + 1] << " ";
        } cout << "\n";*/
        long long dl = 0, dr = 0;
        while(!l.empty() || !r.empty()){
                if(!l.empty() && s * 2 >= (l.back() - dl)){
                        long long f = l.back() - dl;
                        if(s >= f){
                                dr += (s - f) * 2 + f;
                                dl += f;
                        }
                        else{
                                dr += (s + s - f);
                                dl += (f - s) * 2 + (s + s - f);
                        }
                        l.pop_back();
                }
                else if(!r.empty() && s * 2 >= (r.back() - dr)){
                        long long f = r.back() - dr;
                        if(s >= f){
                                dl += (s - f) * 2 + f;
                                dr += f;
                        }
                        else{
                                dl += (s + s - f);
                                dr += (f - s) * 2 + (s + s - f);
                        }
                        r.pop_back();
                }
                else{
                        return false;
                }
                while(!l.empty() && l.back() - dl <= 0){
                        l.pop_back();
                }
                while(!r.empty() && r.back() - dr <= 0){
                        r.pop_back();
                }
        }
        /*for(int i = 0; i + 1 < r.size(); i++){
                cout << r[i] - r[i + 1] << " ";
        }*/
        return true;
}

void solve()
{
        cin >> n >> k >> t;
        for(int i = 1; i <= n; i++){
                cin >> a[i];
        }
        long long l = 1, r = 1e9 + 1;
        //cout << can(6) << endl;
        //return;
        while(l < r){
                long long m = (l + r) / 2;
                if(can(m)){
                        r = m;
                }
                else{
                        l = m + 1;
                }
        }
        cout << l << "\n";
}

bool mtest = false; int main()
{
        //fin("input.txt");
        //fout("output.txt");
        //fin("island.in");
        //fout("island.out");
        ios_base::sync_with_stdio(0);
        int TE = 1;
        if(mtest)
                cin >> TE;
        while(TE--)
                solve();
        return 0;
}

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