Submission #15652180


Source Code Expand

Copy
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define int long long
#define MOD 1000000007
#define mod 998244353
#define ff first
#define ss second
#define pb push_back
#define vi vector<int>
#define pii pair<int,int>
#define vii vector<pii>
#define vvi vector<vi>
#define endl "\n"
using namespace std;
void solve1();
void solve()
{
    int T;cin>>T;
    for(int z=1;z<=T;z++)
    {
        solve1();
    }
}
signed main()
{
    std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    solve1();
    return 0;
}
void solve1()
{
    int n,k;cin>>n>>k;
    int arr[n];
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    sort(arr,arr+n);
    int lo=1,hi=arr[n-1];
    int ans=hi;
    int c=((lo + hi)/2);
    while(lo!=hi)
    {
        c=((lo + hi)/2);
        int f=0;
        for(int i=0;i<n;i++)
        {
            if(arr[i]>c)
            {
                f+=((arr[i]-1)/c);
            }
        }
        if(f>k)
        {
            lo = c;
        }
        else
        {
            hi =c;
            ans=min(ans,c);
        }
        if(lo==hi-1)
        {
            break;
        }

    }
    if(k==0)
    {
        cout<<arr[n-1]<<endl;
    }
    else
    {
        int f=0;
        c=ans-1;
        if(c>0)
        {for(int i=0;i<n;i++)
        {
            if(arr[i]>c)
            {
                f+=((arr[i]-1)/c);
            }
        }
        if(f>k)
        {
            lo = c;
        }
        else
        {
            hi =c;
            ans=min(ans,c);
        }}
        cout<<ans<<endl;
    }
}

Submission Info

Submission Time
Task E - Logs
User rahulmysuru7
Language C++ (GCC 9.2.1)
Score 500
Code Size 1671 Byte
Status AC
Exec Time 86 ms
Memory 5196 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 23
Set Name Test Cases
Sample sample00, sample01, sample02
All handmade03, handmade04, handmade05, handmade06, handmade07, handmade08, handmade09, handmade10, handmade11, handmade12, handmade13, handmade14, handmade15, handmade16, random16, random17, random18, random19, random20, random21, sample00, sample01, sample02
Case Name Status Exec Time Memory
handmade03 AC 8 ms 3520 KB
handmade04 AC 2 ms 3556 KB
handmade05 AC 3 ms 3548 KB
handmade06 AC 25 ms 4380 KB
handmade07 AC 45 ms 5020 KB
handmade08 AC 3 ms 3504 KB
handmade09 AC 2 ms 3520 KB
handmade10 AC 2 ms 3552 KB
handmade11 AC 18 ms 4028 KB
handmade12 AC 35 ms 4768 KB
handmade13 AC 3 ms 3624 KB
handmade14 AC 2 ms 3528 KB
handmade15 AC 68 ms 4924 KB
handmade16 AC 19 ms 5148 KB
random16 AC 67 ms 4724 KB
random17 AC 85 ms 5076 KB
random18 AC 86 ms 5196 KB
random19 AC 60 ms 4608 KB
random20 AC 58 ms 4456 KB
random21 AC 70 ms 4684 KB
sample00 AC 3 ms 3568 KB
sample01 AC 2 ms 3588 KB
sample02 AC 2 ms 3504 KB