oj.uz

Submission #1033685

# Submission time Handle Problem Language Result Execution time Memory
1033685 2024-07-25T04:15:19 Z vjudge1 Stove (JOI18_stove) C++14
0 / 100
 0 ms 348 KB 
//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx,avx2,fma,lzcnt,popcnt")
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define ii pair<int,int>
#define ill pair<ll,ll>
#define el cout<<'\n'
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define int long long
const ll mod=1e9+7;
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
const int nmax=1e5;

void add ( int&a , int b ) { if ((a+=b) > mod ) a -= mod ; }
void sub ( int&a , int b ) { if ((a-=b) < 0 ) a += mod ; }

template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

using namespace std;
int a[nmax+5];
int ans=1e9;
bool check(int dis,int k,int n)
{
    int cnt=0;
    int l=1;
   int res=0;

    while(l<=n)
    {
        cnt++;
        int tmp=a[l]+dis-1;
        int cur=a[l];
        while(tmp>=a[l]&&l<=n)
            l++;
        res+=a[l-1]-cur+1;

    }
     //  cout<<dis<<" "<<cnt;el;
     if(cnt<=k)
        ans=min(ans,res);
    return (cnt<=k);
}
signed main()
{
   ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
   int n,k;
   cin>>n>>k;
   for(int i=1;i<=n;i++)
    cin>>a[i];
   int l=1,r=1e9;
   int res=-1;
   while(l<=r)
   {
       int mid=(l+r)>>1;
       if(check(mid,k,n))
       {
           res=mid;
           r=mid-1;
       }
       else
           l=mid+1;
   }
   cout<<ans;
}

Compilation message

stove.cpp: In function 'int main()':
stove.cpp:57:8: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   57 |    int res=-1;
      |        ^~~

Subtask #1
0 / 20.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 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 30.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 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 50.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 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -