結果
| 問題 | No.507 ゲーム大会(チーム決め) |
| ユーザー |
 touchan4692
|
| 提出日時 | 2019-05-10 01:53:31 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
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 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 57 ms
42,404 KB |
| testcase_01 | AC | 56 ms
37,408 KB |
| testcase_02 | AC | 56 ms
37,356 KB |
| testcase_03 | AC | 57 ms
37,492 KB |
| testcase_04 | AC | 57 ms
37,556 KB |
| testcase_05 | AC | 55 ms
37,352 KB |
| testcase_06 | AC | 56 ms
36,808 KB |
| testcase_07 | AC | 201 ms
41,708 KB |
| testcase_08 | AC | 205 ms
41,844 KB |
| testcase_09 | TLE | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
ソースコード
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」が条件を満たすこともあるので、初期値は -1
int 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 {
}
}
}