Submission #953564

#TimeUsernameProblemLanguageResultExecution timeMemory
953564batsukh2006Stove (JOI18_stove)C++17
0 / 100
0 ms348 KiB
#include<iostream> #include<stdio.h> #include<math.h> #include<map> #include<string> #include<algorithm> #include<vector> #include<string.h> #include<utility> #include<set> #include<cmath> #include<queue> #include<deque> #include<functional> #include<stack> #include<limits.h> #include<iomanip> #include<unordered_map> #include<numeric> #include<tuple> #include<bitset> using namespace std; #define MOD 1000000007 #define int long long #define endl '\n' void solve(){ int n,k; cin>>n>>k; vector<int> a(n+1); for(int i=1; i<=n; i++) cin>>a[i]; int ans=1e12; int l=1,r=1e12; while(l<=r){ int m=l+(r-l)/2; int sum=0,res=0,lst=1; for(int i=1; i<=n; i++){ if(a[i]-a[lst]+1>m){ res+=a[i-1]-a[lst]+1; sum++; lst=i; } if(i==n){ res+=a[i]-a[lst]+1; sum++; } } if(sum<=k){ r=m-1; ans=min(ans,res); }else{ l=m+1; } } cout<<ans; } signed main(){ // freopen("file.in", "r", stdin); // freopen("file.out", "w", stdout); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int T=1; // cin>>T; while(T--){ solve(); cout<<endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...