답안 #62163

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
62163 2018-07-27T15:57:58 Z reality 쌀 창고 (IOI11_ricehub) C++17
100 / 100
54 ms 16508 KB
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()

#include "ricehub.h"


const int N = (int)(1e6) + 5;

ll s[N];

ll ss[N];

ll get(int l,int m,int r)
{
    return (ss[r] - ss[m]) - (r - m) * s[m] + (m - l) * s[m] - (ss[m - 1] - ss[l - 1]);
}

int besthub(int N, int L, int X[], ll B)
{
    int n = N;
    int m = L;
    ll k = B;
    int ans = 0;
    for (int i = 0;i < n;++i)
        s[i + 1] = X[i],ss[i + 1] = ss[i] + s[i + 1];
    for (int i = 1;i <= n;++i)
    {
        int len = 0;
        for (int t = 1 << 17;t;t /= 2)
            if (get(max(1,i - len - t),i,min(n,i + len + t)) <= k)
                len += t;
        int L = max(1,i - len);
        int R = min(n,i + len);
        if (get(L,i,R) <= k)
            ans = max(ans,R - L + 1);
        if (L > 1 && get(L - 1,i,R) <= k)
            ans = max(ans,R - L + 2);
        if (R < n && get(L,i,R + 1) <= k)
            ans = max(ans,R - L + 2);
    }
    return ans;
}

Compilation message

ricehub.cpp: In function 'int besthub(int, int, int*, long long int)':
ricehub.cpp:32:9: warning: unused variable 'm' [-Wunused-variable]
     int m = L;
         ^
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 3 ms 380 KB Output is correct
3 Correct 3 ms 552 KB Output is correct
4 Correct 3 ms 552 KB Output is correct
5 Correct 4 ms 564 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 568 KB Output is correct
2 Correct 2 ms 572 KB Output is correct
3 Correct 2 ms 572 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 4 ms 644 KB Output is correct
6 Correct 3 ms 648 KB Output is correct
7 Correct 0 ms 656 KB Output is correct
8 Correct 6 ms 660 KB Output is correct
9 Correct 3 ms 764 KB Output is correct
10 Correct 3 ms 768 KB Output is correct
11 Correct 3 ms 768 KB Output is correct
12 Correct 3 ms 768 KB Output is correct
13 Correct 3 ms 768 KB Output is correct
14 Correct 3 ms 768 KB Output is correct
15 Correct 3 ms 788 KB Output is correct
16 Correct 3 ms 804 KB Output is correct
17 Correct 2 ms 804 KB Output is correct
18 Correct 3 ms 804 KB Output is correct
19 Correct 4 ms 804 KB Output is correct
20 Correct 3 ms 804 KB Output is correct
21 Correct 3 ms 804 KB Output is correct
22 Correct 4 ms 804 KB Output is correct
23 Correct 3 ms 804 KB Output is correct
24 Correct 3 ms 804 KB Output is correct
25 Correct 3 ms 804 KB Output is correct
26 Correct 4 ms 804 KB Output is correct
27 Correct 4 ms 804 KB Output is correct
28 Correct 3 ms 804 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 804 KB Output is correct
2 Correct 3 ms 804 KB Output is correct
3 Correct 3 ms 804 KB Output is correct
4 Correct 3 ms 804 KB Output is correct
5 Correct 5 ms 804 KB Output is correct
6 Correct 3 ms 804 KB Output is correct
7 Correct 4 ms 804 KB Output is correct
8 Correct 4 ms 804 KB Output is correct
9 Correct 3 ms 804 KB Output is correct
10 Correct 3 ms 804 KB Output is correct
11 Correct 4 ms 804 KB Output is correct
12 Correct 3 ms 808 KB Output is correct
13 Correct 3 ms 832 KB Output is correct
14 Correct 3 ms 840 KB Output is correct
15 Correct 4 ms 848 KB Output is correct
16 Correct 3 ms 852 KB Output is correct
17 Correct 4 ms 852 KB Output is correct
18 Correct 3 ms 864 KB Output is correct
19 Correct 3 ms 872 KB Output is correct
20 Correct 3 ms 880 KB Output is correct
21 Correct 4 ms 980 KB Output is correct
22 Correct 5 ms 1040 KB Output is correct
23 Correct 6 ms 1064 KB Output is correct
24 Correct 4 ms 1064 KB Output is correct
25 Correct 6 ms 1128 KB Output is correct
26 Correct 6 ms 1148 KB Output is correct
27 Correct 6 ms 1296 KB Output is correct
28 Correct 5 ms 1296 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 1672 KB Output is correct
2 Correct 9 ms 1788 KB Output is correct
3 Correct 46 ms 4356 KB Output is correct
4 Correct 39 ms 5416 KB Output is correct
5 Correct 20 ms 5416 KB Output is correct
6 Correct 19 ms 5416 KB Output is correct
7 Correct 34 ms 6852 KB Output is correct
8 Correct 38 ms 7672 KB Output is correct
9 Correct 23 ms 7672 KB Output is correct
10 Correct 17 ms 7672 KB Output is correct
11 Correct 50 ms 9276 KB Output is correct
12 Correct 49 ms 10344 KB Output is correct
13 Correct 28 ms 10344 KB Output is correct
14 Correct 18 ms 10344 KB Output is correct
15 Correct 28 ms 11400 KB Output is correct
16 Correct 30 ms 12236 KB Output is correct
17 Correct 33 ms 13488 KB Output is correct
18 Correct 43 ms 14432 KB Output is correct
19 Correct 54 ms 15504 KB Output is correct
20 Correct 42 ms 16508 KB Output is correct