結果
| 問題 | No.507 ゲーム大会(チーム決め) |
| ユーザー |
 touchan4692
|
| 提出日時 | 2019-05-10 01:53:31 |
| 言語 | Java (openjdk 23) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,926 bytes |
| コンパイル時間 | 2,508 ms |
| コンパイル使用メモリ | 92,500 KB |
| 実行使用メモリ | 47,232 KB |
| 最終ジャッジ日時 | 2024-07-02 00:54:31 |
| 合計ジャッジ時間 | 8,129 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 7 TLE * 1 -- * 11 |
ソースコード
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;import java.io.OutputStream;import java.io.PrintWriter;import java.math.BigDecimal;import java.util.AbstractMap;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.Arrays;import java.util.Comparator;import java.util.Deque;import java.util.HashMap;import java.util.HashSet;import java.util.List;import java.util.Map;import java.util.Queue;import java.util.Set;import java.util.TreeSet;import static java.util.Comparator.*;public class Main {public static void main(String[] args) {InputStream inputStream = System.in;OutputStream outputStream = System.out;MyInput in = new MyInput(inputStream);PrintWriter out = new PrintWriter(outputStream);Solver solver = new Solver();solver.solve(1, in, out);out.close();}// ======================================================================//static class Solver {int N,M;long[] A;long[] R;// index が条件を満たすかどうかboolean isOK(long val, int pair, PrintWriter out) {long score = val + A[pair];// out.println("call : (val = " + val + ") + (A[" + pair + "] = " + A[pair] + ") = " + score);int cnt = 0, sv = 0;for(int i = N-2; i >= 0; i--) {if(i == pair) continue;if(i <= sv) break;for(int j = sv; j < i; j++) {if(j == pair) continue;if(A[i] + A[j] > score) {sv = j+1;cnt++;// out.println("(A[" + i + "] = " + A[i] + ") + A[" + sv// + "] = " + A[sv] + ") > " + score + " --> cnt = " + cnt);break;}}if(cnt >= M) break;}if(cnt < M) return true;else return false;}// 汎用的な二分探索のテンプレ// この場合、key より大きい中で 一番左のインデックスを返すint calc(long a, PrintWriter out) {int ng = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1int ok = A.length; // 「index = a.length-1」が条件を満たさないこともあるので、初期値は a.length()while (Math.abs(ok - ng) > 1) {int mid = (ok + ng) / 2;if (isOK(a, mid, out)) ok = mid;else ng = mid;}if(ok >=0 && ok < A.length) return (int)A[ok];else return -1;}public void solve(int testNumber, MyInput in, PrintWriter out) {N = in.nextInt();M = in.nextInt();A = new long[N-1];R = new long[N-1];long a = in.nextLong();for(int i=0; i < N-1; i++) {A[i] = in.nextLong();}Arrays.sort(A);R[N-2] = A[N-2];for(int i=N-3; i >= 0; i--) {R[i] += R[i+1] + A[i];}out.println(calc(a, out));}}// ======================================================================static class Pair<K, V> extends AbstractMap.SimpleEntry<K, V> {/** serialVersionUID. */private static final long serialVersionUID = 6411527075103472113L;public Pair(final K key, final V value) {super(key, value);}}static class MyInput {private final BufferedReader in;private static int pos;private static int readLen;private static final char[] buffer = new char[1024 * 8];private static char[] str = new char[500 * 8 * 2];private static boolean[] isDigit = new boolean[256];private static boolean[] isSpace = new boolean[256];private static boolean[] isLineSep = new boolean[256];static {for (int i = 0; i < 10; i++) {isDigit['0' + i] = true;}isDigit['-'] = true;isSpace[' '] = isSpace['\r'] = isSpace['\n'] = isSpace['\t'] = true;isLineSep['\r'] = isLineSep['\n'] = true;}public MyInput(InputStream is) {in = new BufferedReader(new InputStreamReader(is));}public int read() {if (pos >= readLen) {pos = 0;try {readLen = in.read(buffer);} catch (IOException e) {throw new RuntimeException();}if (readLen <= 0) {throw new MyInput.EndOfFileRuntimeException();}}return buffer[pos++];}public int nextInt() {int len = 0;str[len++] = nextChar();len = reads(len, isSpace);int i = 0;int ret = 0;if (str[0] == '-') {i = 1;}for (; i < len; i++) ret = ret * 10 + str[i] - '0';if (str[0] == '-') {ret = -ret;}return ret;}public long nextLong() {int len = 0;str[len++] = nextChar();len = reads(len, isSpace);int i = 0;long ret = 0L;if (str[0] == '-') {i = 1;}for (; i < len; i++) ret = ret * 10 + str[i] - '0';if (str[0] == '-') {ret = -ret;}return ret;}public String nextString() {String ret = new String(nextDChar()).trim();return ret;}public char[] nextDChar() {int len = 0;len = reads(len, isSpace);char[] ret = new char[len + 1];for (int i=0; i < len; i++) ret[i] = str[i];ret[len] = 0x00;return ret;}public char nextChar() {while (true) {final int c = read();if (!isSpace[c]) {return (char) c;}}}int reads(int len, boolean[] accept) {try {while (true) {final int c = read();if (accept[c]) {break;}if (str.length == len) {char[] rep = new char[str.length * 3 / 2];System.arraycopy(str, 0, rep, 0, str.length);str = rep;}str[len++] = (char) c;}} catch (MyInput.EndOfFileRuntimeException e) {}return len;}static class EndOfFileRuntimeException extends RuntimeException {}}}