oj.uz

Submission #581861

# Submission time Handle Problem Language Result Execution time Memory
581861 2022-06-23T07:29:44 Z 반딧불(#8365) Sparklers (JOI17_sparklers) C++17
0 / 100
 1 ms 212 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, k;
ll t;
ll arr[100002];
ll val[100002];
ll revVal[100002];

void makeVector(vector<pair<ll, ll> > &ret, vector<ll> vec){
    ll sum = 0, minSum = 0;
    for(auto x: vec){
        if(sum>0 && x<0){
            ret.push_back(make_pair(-minSum, sum));
            sum = minSum = 0;
        }
        sum += x;
        minSum = min(minSum, sum);
    }
    if(sum || minSum) ret.push_back(make_pair(-minSum, sum));
    ret.push_back(make_pair(5e18, -5e18));
}

bool able(ll speed){
    speed*=t*2;
    if(speed==6){
        #ifdef TEST
        puts("");
        #endif // TEST
    }
    for(int i=1; i<n; i++) val[i] = revVal[n-i] = speed - (arr[i+1] - arr[i]);

    /// ����, ������ �ٵ��
    vector<pair<ll, ll> > Avec, Bvec;
    makeVector(Avec, vector<ll>(revVal+(n+1-k), revVal+n));
    makeVector(Bvec, vector<ll>(val+k, val+n));

    ll val = 0;
    int a = 0, b = 0;
    int al = (int)Avec.size()-1, bl = (int)Bvec.size()-1;

    for(int i=0; i<al-2; i++) assert(Avec[i].second >= 0);
    for(int i=0; i<bl-2; i++) assert(Bvec[i].second >= 0);

    while(a<al-1 || b<bl-1){
        if(a<al-1 && b<bl-1 && Avec[a].first <= val && Bvec[b].first <= val){ /// �� �� ���� �� ����
            if(Avec[a].second >= Bvec[b].second) val += Avec[a++].second;
            else val += Bvec[b++].second;
        }
        else if(a<al-1 && Avec[a].first <= val){
            val += Avec[a++].second;
        }
        else if(b<bl-1 && Bvec[b].first <= val){
            val += Bvec[b++].second;
        }
        else return false;
        if(val<0) exit(1);
    }
    if(a>=al && b>=bl) return true;
    else if(a>=al){
        while(b<bl){
            if(Bvec[b].first > val) return false;
            val += Bvec[b++].second;
            if(val<0) return false;
        }
        return true;
    }
    else if(b>=bl){
        while(a<al){
            if(Avec[a].first > val) return false;
            val += Avec[a++].second;
            if(val<0) return false;
        }
        return true;
    }

    assert(a==al-1 && b==bl-1);
    /// �ϳ��� ���� ����
    vector<pair<ll, ll> > vec = {Avec[a], Bvec[b]};
    if(val >= vec[0].first && val+vec[0].second >= vec[1].first && val+vec[0].second+vec[1].second >= 0) return true;
    if(val >= vec[1].first && val+vec[1].second >= vec[0].first && val+vec[1].second+vec[0].second >= 0) return true;
    return false;
}

int main(){
    scanf("%d %d %lld", &n, &k, &t);
    for(int i=1; i<=n; i++) scanf("%lld", &arr[i]);

    ll L = 0, R = 1e9, ANS = 1e9;
    while(L<=R){
        ll MID = (L+R)/2;
        if(able(MID)) ANS = MID, R = MID-1;
        else L = MID+1;
    }
    printf("%lld", ANS);
}

Compilation message

sparklers.cpp: In function 'int main()':
sparklers.cpp:89:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |     scanf("%d %d %lld", &n, &k, &t);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sparklers.cpp:90:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |     for(int i=1; i<=n; i++) scanf("%lld", &arr[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -