oj.uz

Submission #1003268

# Submission time Handle Problem Language Result Execution time Memory
1003268 2024-06-20T08:22:29 Z vjudge1 Rice Hub (IOI11_ricehub) C++17
42 / 100
 1000 ms 3540 KB 
#include<bits/stdc++.h>
#include "ricehub.h"
#define ll long long
#define ld long double
#define vl vector<ll>
#define vi vector<int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define f first
#define s second
#define pb push_back
#define p_b pop_back
using namespace std;
int besthub(int R, int L, int X[], long long B)
{
    ll n = R, i, j, ans = 0;
    ll h[n+5], pref[n+5];
    ll l = 1, r = L;
    vl v;
    v.pb(LLONG_MIN);
    pref[0] = 0;
    for(i = 1; i <= n; i++)
    {
        h[i] = X[i-1];
        pref[i] = pref[i-1] + h[i];
        v.pb(X[i-1]);
    }
    L = min(L, (int)h[n]);
    for(ll mid = 0; mid <= L; mid++)
    {
        ll lb = lower_bound(all(v), mid) - v.begin();
        ll tl = lb - 1, tr = lb + 1, sum1 = 0, sum2 = 0;
        if(h[lb] != mid)
            tr = lb;
        //cout << "mid: " << mid << " lb: " << lb << "\n";
        while((tl >= 1 && tl <= n) || (tr >= 1 && tr <= n))
        {
            ll cost1 = LLONG_MAX, cost2 = LLONG_MAX;
            if(tl >= 1 && tl <= n)
                cost1 = mid - h[tl];
            if(tr >= 1 && tr <= n)
                cost2 = h[tr] - mid;
            //cout << "cost1: " << cost1 << " cost2: " << cost2 << "\n";
            if(cost1 == LLONG_MAX && cost2 == LLONG_MAX)
                break;
            if(cost1 <= cost2){
                sum1 += cost1;
                tl--;
            }
            else{
                sum2 += cost2;
                tr++;
            }
            if(sum1 + sum2 > B)
            {
                if(cost1 <= cost2){
                    sum1 -= cost1;
                    tl++;
                }
                else{
                    sum2 -= cost2;
                    tr--;
                }
                break;
            }
        }
        //cout << "sum1: " << sum1 << " sum2: " << sum2 << "\n";
        tl++, tr--;
        //cout << "tl: " << tl << " tr: " << tr << "\n";
        ans = max(ans, (tr - tl + 1));
    }
    return ans;
}

Compilation message

ricehub.cpp: In function 'int besthub(int, int, int*, long long int)':
ricehub.cpp:18:18: warning: unused variable 'j' [-Wunused-variable]
   18 |     ll n = R, i, j, ans = 0;
      |                  ^
ricehub.cpp:20:8: warning: unused variable 'l' [-Wunused-variable]
   20 |     ll l = 1, r = L;
      |        ^
ricehub.cpp:20:15: warning: unused variable 'r' [-Wunused-variable]
   20 |     ll l = 1, r = L;
      |               ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 6 ms 348 KB Output is correct
24 Correct 6 ms 348 KB Output is correct
25 Correct 11 ms 344 KB Output is correct
26 Correct 11 ms 348 KB Output is correct
27 Correct 2 ms 348 KB Output is correct
28 Correct 2 ms 456 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Execution timed out 1094 ms 348 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1116 KB Output is correct
2 Correct 20 ms 1364 KB Output is correct
3 Execution timed out 1067 ms 3540 KB Time limit exceeded
4 Halted 0 ms 0 KB -