結果
問題 | No.78 クジ付きアイスバー |
ユーザー |
![]() |
提出日時 | 2020-10-03 10:44:45 |
言語 | Java (openjdk 23) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,004 bytes |
コンパイル時間 | 2,144 ms |
コンパイル使用メモリ | 77,516 KB |
実行使用メモリ | 56,368 KB |
最終ジャッジ日時 | 2024-07-18 04:11:25 |
合計ジャッジ時間 | 8,137 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 17 WA * 18 |
ソースコード
import java.io.PrintWriter;import java.util.Scanner;public class Main{public static void main(String[] args) {Scanner scanner=new Scanner(System.in);PrintWriter out=new PrintWriter(System.out);int n=Integer.parseInt(scanner.next());long k=Long.parseLong(scanner.next());String s=scanner.next();long[][] nx=new long[32][51];final long INF=(long)1e12;for(int i=0; i<n; i++) {int sum=0;for(int j=i; j<i+n; j++) {int x=s.charAt(j%n)-'0';sum+=x;if(sum+1==j-i+1) {nx[0][i]=j+1;break;}}if(nx[0][i]==0) {nx[0][i]=INF;}}for(int i=1; i<=30; i++) {for(int j=0; j<n; j++) {long x=nx[i-1][j];if(x==INF) {nx[i][j]=INF;}else{nx[i][j]=Math.min(INF, x/n*n+nx[i-1][(int) (x%n)]);}}}long ans=0;int x=0;for(int i=30; i>=0; i--) {if(nx[i][x]<k) {ans+=(1<<i);x=(int)nx[i][x]%n;k-=nx[i][x]/n*n;}}out.println(ans+1);out.close();scanner.close();}}