結果
問題 | No.78 クジ付きアイスバー |
ユーザー |
|
提出日時 | 2020-05-30 11:06:14 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 5 ms / 5,000 ms |
コード長 | 554 bytes |
コンパイル時間 | 3,471 ms |
コンパイル使用メモリ | 193,252 KB |
最終ジャッジ日時 | 2025-01-10 19:16:29 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 35 |
ソースコード
#include <bits/stdc++.h>#define rep(i,n) for(int i=0;i<(n);i++)using namespace std;using lint=long long;int main(){int n,k;string s; cin>>n>>k>>s;vector<int> sum(n+1);rep(i,n) sum[i+1]=sum[i]+(s[i]-'0');lint lo=0,hi=k;while(hi-lo>1){lint mi=(lo+hi)/2;lint cnt=0,x=mi;for(int t=0;x>0;t++){if(cnt>=k || t>3000){cnt=k;break;}lint c1=sum[n]*(cnt/n)+sum[cnt%n];cnt+=x;lint c2=sum[n]*(cnt/n)+sum[cnt%n];x=c2-c1;}if(cnt>=k) hi=mi;else lo=mi;}printf("%lld\n",hi);return 0;}