結果
問題 | No.1211 円環はお断り |
ユーザー |
![]() |
提出日時 | 2020-08-30 14:52:08 |
言語 | Java (openjdk 23) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,351 bytes |
コンパイル時間 | 2,195 ms |
コンパイル使用メモリ | 77,940 KB |
実行使用メモリ | 91,608 KB |
最終ジャッジ日時 | 2024-11-23 16:17:14 |
合計ジャッジ時間 | 14,082 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 40 TLE * 1 |
ソースコード
import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.HashSet;import java.util.Set;public class Main {static int n, k;static int[] a;public static void main(String[] args) throws Exception {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String[] sa = br.readLine().split(" ");n = Integer.parseInt(sa[0]);k = Integer.parseInt(sa[1]);sa = br.readLine().split(" ");long sum = 0;a = new int[n];for (int i = 0; i < n; i++) {a[i] = Integer.parseInt(sa[i]);sum += a[i];}br.close();long ok = 0;long ng = sum / k + 1;while (Math.abs(ok - ng) > 1) {long mid = (ok + ng) / 2;if (can(mid)) {ok = mid;} else {ng = mid;}}System.out.println(ok);}static boolean can(long mid) {Set<Integer> set = new HashSet<>();for (int i = 0; i < n; i++) {if (set.contains(i - 1)) {break;}long sum = 0;for (int j = i; j < i + n; j++) {int idx = j % n;sum += a[idx];if (sum >= mid) {set.add(idx);break;}}}for (int i : set) {long sum = 0;int cnt = 0;for (int j = i + 1; j <= i + n; j++) {int idx = j % n;sum += a[idx];if (sum >= mid) {cnt++;sum = 0;}}if (cnt >= k) {return true;}}return false;}}