oj.uz

답안 #614273

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
614273 2022-07-31T00:26:34 Z nohaxjustsoflo 쌀 창고 (IOI11_ricehub) C++17
42 / 100
 145 ms 2556 KB 
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> order_set;
mt19937 mt_rand(chrono::high_resolution_clock::now().time_since_epoch().count());
//uniform_int_distribution<int> gen; ///(min, max)
//int random() {return gen(mt_rand);}
const int mxN=1e5+5;
const int mod=998244353;
const int mxlogN=40;
const int mxK=26;
const int inf=2e9;
const int K=600;
ll a[mxN], p[mxN];
//#include "ricehub.h"
int besthub(int n, int L, int A[], ll B)
{
    for(int i=0; i<n; i++) a[i]=A[i];
    ll s=0;
    for(int i=0; i<n; i++) p[i]=s+=a[i];
    ll ans=0;
    for(ll i=0; i<n; i++)
    {
        ll l=0, r=1e9;
        while(r-l>1)
        {
            int m=(l+r)/2;
            int r2=prev(upper_bound(a,a+n,a[i]+m))-a;
            int l2=lower_bound(a,a+n,a[i]-m)-a;
            ll cost=0;
            cost+=p[r2]-p[i]-(r2-i)*a[i];
            cost+=(i-l2)*a[i]-((i?p[i-1]:0)-(l2?p[l2-1]:0));
            if(cost<=B) l=m;
            else r=m;
        }
        int r2=prev(upper_bound(a,a+n,a[i]+l))-a;
        int l2=lower_bound(a,a+n,a[i]-l)-a;
        ll cost=0;
        cost+=p[r2]-p[i]-(r2-i)*a[i];
        cost+=(i-l2)*a[i]-((i?p[i-1]:0)-(l2?p[l2-1]:0));
        ans=max(ans,r2-l2+1+(B-cost)/r);

    }
    return ans;
}
/*
int besthub2(int n, int L, int X[], ll B)
{
    int ans=0;
    for(int i=0; i<n; i++)
    {
        int p=X[i];
        vector<int> a(n);
        for(int i=0; i<n; i++) a[i]=abs(X[i]-p);
        sort(a.begin(),a.end());
        ll x=B;
        int j=0;
        while(j<n&&a[j]<=x) x-=a[j++];
        cout << "i " << i << " " << j << "\n";
        ans=max(ans,j);
    }
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, L, B; cin >> n >> L >> B;
    int a[n];
    for(int i=0; i<n; i++) cin >> a[i];
    cout << besthub(n,L,a,B) << " " << besthub2(n,L,a,B);
    return 0;
    /*
    while(1)
    {
        int n=mt_rand()%5+1, L=0, B=mt_rand()%10;
        int a[n];
        for(int i=0; i<n; i++) a[i]=mt_rand()%15;
        sort(a,a+n);
        if(besthub(n,L,a,B)!=besthub2(n,L,a,B))
        {
            cout << n << " " << B << "\n";
            for(int i=0; i<n; i++) cout << a[i] << " ";
            cout << "\n";
            return 0;
        }
    }
}*/


/*
5 0 7
5 10 11 11 11
*/

Compilation message

ricehub.cpp:81:5: warning: "/*" within comment [-Wcomment]
   81 |     /*
      |

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 2 ms 212 KB Output is correct
27 Correct 2 ms 340 KB Output is correct
28 Correct 2 ms 340 KB Output is correct

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 2 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 840 KB Output is correct
2 Correct 48 ms 828 KB Output is correct
3 Incorrect 145 ms 2556 KB Output isn't correct
4 Halted 0 ms 0 KB -