Submission #1479714
Source Code Expand
import java.io.*; import java.util.*; public class Main { static ContestScanner in; static Writer out; public static void main(String[] args) { Main main = new Main(); try { in = new ContestScanner(); out = new Writer(); main.solve(); out.close(); in.close(); } catch (IOException e) { e.printStackTrace(); } } void solve() throws IOException { int n = in.nextInt(); int k = in.nextInt(); long[] a = new long[n]; for (int i = 0; i < n; i++) { a[i] = in.nextInt(); } int sz = 1 << n; long min = Long.MAX_VALUE; for (int i = 0; i < sz; i++) { long cost = 0; long pre = 0; int cnt = 0; for (int j = 0; j < n; j++) { if(a[j] > pre) cnt++; if((i & 1 << j) > 0) { long add = pre < a[j] ? 0 : pre + 1 - a[j]; cost += add; if(add > 0) cnt++; pre++; } pre = Math.max(pre, a[j]); } if(cnt < k) continue; min = Math.min(min, cost); } System.out.println(min); } } @SuppressWarnings("serial") class MultiSet<T> extends HashMap<T, Long>{ @Override public Long get(Object key){return containsKey(key)?super.get(key):0L;} public void add(T key,long v){put(key,get(key)+v);} public void add(T key){put(key,get(key)+1);} public void sub(T key){final long v=get(key);if(v==1)remove(key);else put(key,v-1);} public MultiSet<T> merge(MultiSet<T> set) {MultiSet<T>s,l;if(this.size()<set.size()){s=this;l=set;}else{s=set;l=this;} for(Entry<T,Long>e:s.entrySet())l.add(e.getKey(),e.getValue());return l;} } class Writer extends PrintWriter{ public Writer(String filename)throws IOException {super(new BufferedWriter(new FileWriter(filename)));} public Writer()throws IOException{super(System.out);} } class ContestScanner implements Closeable{ private BufferedReader in;private int c=-2; public ContestScanner()throws IOException {in=new BufferedReader(new InputStreamReader(System.in));} public ContestScanner(String filename)throws IOException {in=new BufferedReader(new InputStreamReader(new FileInputStream(filename)));} public String nextToken()throws IOException { StringBuilder sb=new StringBuilder(); while((c=in.read())!=-1&&Character.isWhitespace(c)); while(c!=-1&&!Character.isWhitespace(c)){sb.append((char)c);c=in.read();} return sb.toString(); } public String readLine()throws IOException{ StringBuilder sb=new StringBuilder();if(c==-2)c=in.read(); while(c!=-1&&c!='\n'&&c!='\r'){sb.append((char)c);c=in.read();} return sb.toString(); } public long nextLong()throws IOException,NumberFormatException {return Long.parseLong(nextToken());} public int nextInt()throws NumberFormatException,IOException {return(int)nextLong();} public double nextDouble()throws NumberFormatException,IOException {return Double.parseDouble(nextToken());} public void close() throws IOException {in.close();} }
Submission Info
Submission Time | |
---|---|
Task | B - Buildings are Colorful! |
User | threepipes_s |
Language | Java8 (OpenJDK 1.8.0) |
Score | 350 |
Code Size | 3384 Byte |
Status | AC |
Exec Time | 102 ms |
Memory | 22868 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | Subtask3 | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 120 / 120 | 90 / 90 | 140 / 140 | ||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | sub0_in1.txt, sub0_in2.txt |
Subtask1 | sub1_in1.txt, sub1_in2.txt |
Subtask2 | sub2_in1.txt, sub2_in2.txt, sub2_in3.txt |
Subtask3 | sub0_in1.txt, sub0_in2.txt, sub1_in1.txt, sub1_in2.txt, sub2_in1.txt, sub2_in2.txt, sub2_in3.txt, sub3_in1.txt, sub3_in2.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sub0_in1.txt | AC | 69 ms | 20308 KB |
sub0_in2.txt | AC | 70 ms | 19156 KB |
sub1_in1.txt | AC | 93 ms | 18000 KB |
sub1_in2.txt | AC | 83 ms | 20692 KB |
sub2_in1.txt | AC | 83 ms | 18644 KB |
sub2_in2.txt | AC | 70 ms | 18772 KB |
sub2_in3.txt | AC | 75 ms | 21076 KB |
sub3_in1.txt | AC | 102 ms | 19796 KB |
sub3_in2.txt | AC | 84 ms | 22868 KB |