oj.uz

Submission #585575

# Submission time Handle Problem Language Result Execution time Memory
585575 2022-06-29T05:37:02 Z 반딧불(#8385) MP3 Player (CEOI10_mp3player) C++17
0 / 100
 1000 ms 3420 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>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));

    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(0, mid, 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:29:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     scanf("%d %lld %lld", &n, &k, &goal);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mp3player.cpp:33:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         scanf(" %c %lld", &c, &arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 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 Incorrect 49 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 76 ms 384 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 1096 ms 920 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 1086 ms 1108 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 1086 ms 1108 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 1053 ms 1744 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 1088 ms 3300 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 1086 ms 3420 KB Time limit exceeded
2 Halted 0 ms 0 KB -