oj.uz

Submission #585582

# Submission time Handle Problem Language Result Execution time Memory
585582 2022-06-29T05:44:14 Z 반딧불(#8385) MP3 Player (CEOI10_mp3player) C++17
10 / 100
 1000 ms 2252 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n; ll k, goal;
bool op[100002];
ll arr[100002];
vector<ll> vec;
ll ans, ansV;

pair<ll, ll> calc(ll l, ll r, ll lim){
    ll last = -1e18;
    for(int i=1; i<=n; i++){
        if(last == -1 || last+lim < arr[i]) last = arr[i];
        else{
            last = arr[i];
            if(op[i]) l++, r++;
            else l--, r--;
            if(l<0) l=0;
            if(r<0) r=0;
            if(l>k) l=k;
            if(r>k) r=k;
        }
    }
    return make_pair(l, r);
}

int main(){
    scanf("%d %lld %lld", &n, &k, &goal);
    ansV = goal;
    for(int i=1; i<=n; i++){
        char c;
        scanf(" %c %lld", &c, &arr[i]);
        if(c == '+') op[i] = 1;
    }

    for(int i=1; i<n; i++) vec.push_back(arr[i+1] - arr[i]);
    vec.push_back(0);
    vec.push_back(ll(3e9));
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());

    for(ll lim: vec){
        pair<ll, ll> c = calc(0, k, lim);
        ll l = c.first, r = c.second;
        if(l<=goal && goal<=r && ans < lim){
            ans = lim;

            ll s = 0, e = k;
            while(s <= e){
                ll mid = (s+e)/2;
                auto p = calc(mid, k, lim);
                if(p.first <= goal && goal <= p.second) ansV = mid, s = mid+1;
                else e = mid-1;
            }
        }
    }
    if(ans > 2e9) printf("infinity");
    else printf("%lld %lld", ans, ansV);
}

Compilation message

mp3player.cpp: In function 'int main()':
mp3player.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |     scanf("%d %lld %lld", &n, &k, &goal);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mp3player.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |         scanf(" %c %lld", &c, &arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 340 KB Output is correct
2 Correct 34 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 4 ms 340 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 388 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1081 ms 852 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1082 ms 852 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 852 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1089 ms 1360 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1084 ms 2252 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 2252 KB Time limit exceeded
2 Halted 0 ms 0 KB -