結果
問題 | No.78 クジ付きアイスバー |
ユーザー |
|
提出日時 | 2020-09-06 15:41:34 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 20 ms / 5,000 ms |
コード長 | 952 bytes |
コンパイル時間 | 1,929 ms |
コンパイル使用メモリ | 197,952 KB |
最終ジャッジ日時 | 2025-01-14 07:50:29 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 35 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define REP(i,n) for(int i=0; i<(int)(n); i++)const long long INF = 1LL<<50;int main() {ios_base::sync_with_stdio(0);cin.tie(0);int n;long long k;string s;cin >> n >> k >> s;vector<vector<long long> > dp(50, vector<long long>(n));for (int i = 0; i < n; i++) {long long cnt = 0;int r = 1;int j = i;while (r > 0) {if (++cnt > n) break;--r;r += s[j] - '0';++j %= n;}if (cnt > n)dp[0][i] = INF;elsedp[0][i] = cnt;}for (int i = 1; i < 50; i++) {for (int j = 0; j < n; j++) {dp[i][j] = min(dp[i-1][j] + dp[i-1][(j + dp[i-1][j]) % n], INF);}}int cur = 0;long long ret = 0;for (int i = 49; i >= 0; i--) {if (k > dp[i][cur]) {k -= dp[i][cur];ret += 1LL<<i;cur = (cur + dp[i][cur]) % n;}}cout << ++ret << endl;return 0;}