結果
問題 | No.1095 Smallest Kadomatsu Subsequence |
ユーザー |
![]() |
提出日時 | 2020-06-26 21:43:13 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 1,372 ms / 2,000 ms |
コード長 | 8,078 bytes |
コンパイル時間 | 2,494 ms |
コンパイル使用メモリ | 83,008 KB |
実行使用メモリ | 77,704 KB |
最終ジャッジ日時 | 2024-07-04 20:24:35 |
合計ジャッジ時間 | 17,834 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
import java.io.*;import java.math.BigDecimal;import java.util.*;@SuppressWarnings("unused")public class Main {FastScanner in;PrintWriter out;final static int MOD = (int)1e9+7;void solve(){int N = in.nextInt();long[] A = in.nextLongArray(N);MultiSet<Long> L = new MultiSet<>(), R = new MultiSet<>();for(int i = 0; i < N; i++) R.add(A[i]);long min = Long.MAX_VALUE;for(int i = 0; i < N; i++){R.sub(A[i]);if(!L.isEmpty() && !R.isEmpty()){Long vl = L.firstKey(), vr = R.firstKey();if(vl != null && vr != null && vl < A[i] && vr < A[i]) min = Math.min(min, vl + A[i] + vr);}{Long vl = L.higherKey(A[i]), vr = R.higherKey(A[i]);if(vl != null && vr != null) min = Math.min(min, vl + A[i] + vr);}L.add(A[i]);}out.println(min == Long.MAX_VALUE ? "-1" : min);}class MultiSet<K extends Comparable<K>> extends TreeMap<K,Integer>{int sum = 0;public int sum(){return this.sum;}public int count(K k){return this.getOrDefault(k, 0);}public int add(K k) {int res = this.count(k) + 1;this.put(k, res);sum++;return res;}public int sub(K k){if(!this.containsKey(k)) return -1;int res = this.count(k) - 1;if(res == 0) this.remove(k);else this.put(k, res);sum--;return res;}public int subAll(K k){if(!this.containsKey(k)) return -1;int cnt = this.count(k);this.remove(k);sum -= cnt;return cnt;}}public static void main(String[] args) {new Main().m();}private void m() {in = new FastScanner(System.in);out = new PrintWriter(System.out);/*try {String path = "input.txt";out = new PrintWriter(new BufferedWriter(new FileWriter(new File(path))));}catch (IOException e){e.printStackTrace();}*/solve();out.flush();in.close();out.close();}static class FastScanner {private Reader input;public FastScanner() {this(System.in);}public FastScanner(InputStream stream) {this.input = new BufferedReader(new InputStreamReader(stream));}public void close() {try {this.input.close();} catch (IOException e) {e.printStackTrace();}}public int nextInt() {long nl = nextLong();if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();return (int) nl;}public long nextLong() {try {int sign = 1;int b = input.read();while ((b < '0' || '9' < b) && b != '-' && b != '+') {b = input.read();}if (b == '-') {sign = -1;b = input.read();} else if (b == '+') {b = input.read();}long ret = b - '0';while (true) {b = input.read();if (b < '0' || '9' < b) return ret * sign;ret *= 10;ret += b - '0';}} catch (IOException e) {e.printStackTrace();return -1;}}public double nextDouble() {try {double sign = 1;int b = input.read();while ((b < '0' || '9' < b) && b != '-' && b != '+') {b = input.read();}if (b == '-') {sign = -1;b = input.read();} else if (b == '+') {b = input.read();}double ret = b - '0';while (true) {b = input.read();if (b < '0' || '9' < b) break;ret *= 10;ret += b - '0';}if (b != '.') return sign * ret;double div = 1;b = input.read();while ('0' <= b && b <= '9') {ret *= 10;ret += b - '0';div *= 10;b = input.read();}return sign * ret / div;} catch (IOException e) {e.printStackTrace();return Double.NaN;}}public char nextChar() {try {int b = input.read();while (Character.isWhitespace(b)) {b = input.read();}return (char) b;} catch (IOException e) {e.printStackTrace();return 0;}}public String nextStr() {try {StringBuilder sb = new StringBuilder();int b = input.read();while (Character.isWhitespace(b)) {b = input.read();}while (b != -1 && !Character.isWhitespace(b)) {sb.append((char) b);b = input.read();}return sb.toString();} catch (IOException e) {e.printStackTrace();return "";}}public String nextLine() {try {StringBuilder sb = new StringBuilder();int b = input.read();while (b != -1 && b != '\n') {sb.append((char) b);b = input.read();}return sb.toString();} catch (IOException e) {e.printStackTrace();return "";}}public int[] nextIntArray(int n) {int[] res = new int[n];for (int i = 0; i < n; i++) {res[i] = nextInt();}return res;}public int[] nextIntArrayDec(int n) {int[] res = new int[n];for (int i = 0; i < n; i++) {res[i] = nextInt() - 1;}return res;}public int[] nextIntArray1Index(int n) {int[] res = new int[n + 1];for (int i = 0; i < n; i++) {res[i + 1] = nextInt();}return res;}public long[] nextLongArray(int n) {long[] res = new long[n];for (int i = 0; i < n; i++) {res[i] = nextLong();}return res;}public long[] nextLongArrayDec(int n) {long[] res = new long[n];for (int i = 0; i < n; i++) {res[i] = nextLong() - 1;}return res;}public long[] nextLongArray1Index(int n) {long[] res = new long[n + 1];for (int i = 0; i < n; i++) {res[i + 1] = nextLong();}return res;}public double[] nextDoubleArray(int n) {double[] res = new double[n];for (int i = 0; i < n; i++) {res[i] = nextDouble();}return res;}}}