oj.uz

Submission #1027101

# Submission time Handle Problem Language Result Execution time Memory
1027101 2024-07-18T21:34:03 Z kkkkkkkk Rice Hub (IOI11_ricehub) C++14
100 / 100
 13 ms 4196 KB 
#include <bits/stdc++.h>

using namespace std;

vector<int> v;
long long B;
long long pref_sum[100005];

bool proveri(int k) {
    for (int i=0;i<=v.size()-k;i++) {
        int poz=(i+i+k)/2;
        int hub=v[poz];
        long long zbir_levo=hub*(poz-i)-(pref_sum[poz]-pref_sum[i]+v[i]-v[poz]);
        long long zbir_desno=(pref_sum[i+k-1]-pref_sum[poz]+v[poz])-hub*(i+k-poz);
        if (zbir_levo+zbir_desno<=B) return true;
    }
    return false;
}

int besthub(int R, int L, int a[], long long b) {
    B=b;
    for (int i=0;i<R;i++)
        v.push_back(a[i]);
    pref_sum[0]=a[0];
    for (int i=1;i<R;i++)
        pref_sum[i]=pref_sum[i-1]+a[i];
    int l=1, r=R+1;
    while (l+1<r) {
        int mid=(l+r)/2;
        if (proveri(mid)) l=mid;
        else r=mid;
    }
    return l;
}

Compilation message

ricehub.cpp: In function 'bool proveri(int)':
ricehub.cpp:10:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for (int i=0;i<=v.size()-k;i++) {
      |                  ~^~~~~~~~~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
25.0 / 25.0

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

Subtask #3
26.0 / 26.0

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

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 3 ms 2788 KB Output is correct
3 Correct 8 ms 3032 KB Output is correct
4 Correct 8 ms 3032 KB Output is correct
5 Correct 5 ms 2872 KB Output is correct
6 Correct 5 ms 3288 KB Output is correct
7 Correct 7 ms 3800 KB Output is correct
8 Correct 7 ms 3908 KB Output is correct
9 Correct 5 ms 3164 KB Output is correct
10 Correct 6 ms 3288 KB Output is correct
11 Correct 9 ms 4056 KB Output is correct
12 Correct 9 ms 4196 KB Output is correct
13 Correct 6 ms 3288 KB Output is correct
14 Correct 5 ms 3288 KB Output is correct
15 Correct 7 ms 3920 KB Output is correct
16 Correct 7 ms 3800 KB Output is correct
17 Correct 8 ms 4056 KB Output is correct
18 Correct 8 ms 4056 KB Output is correct
19 Correct 13 ms 4012 KB Output is correct
20 Correct 12 ms 4052 KB Output is correct