Submission #3423977
Source Code Expand
import java.util.*; class Main { public static void main (String[] args) { Scanner sc = new Scanner(System.in); int d = sc.nextInt(); long G = sc.nextLong() / 100; int[] p = new int[d], g = new int[d], max = new int[d]; int k = (int)Math.pow(2, d); for(int i = 0; i < d; i++){ p[i] = sc.nextInt(); g[i] = sc.nextInt() / 100; max[i] = (i + 1) * p[i] + g[i]; } int ans = Integer.MAX_VALUE; for(int i = 0; i < k; i++){ long gg = G; String kk = to2(i, d); int tmp = 0; int min = -1; for(int j = 0; j < d; j++){ if(kk.charAt(j) == '1'){ gg -= max[j]; tmp += p[j]; }else{ min = j; } } if(min >= 0){ if(gg < (min + 1) * p[min]){ tmp += Math.min((Math.max(gg, 0) + min) / (min + 1), p[min]); } else tmp = Integer.MAX_VALUE; } // else if(min == -1 && gg > 0) tmp = Integer.MAX_VALUE; // else tmp = Integer.MAX_VALUE; // System.out.println(kk + " " + tmp); ans = Math.min(ans, tmp); } System.out.println(ans); } static String to2 (int m, int d){ String ans = ""; for(int i = 0; i < d; i++){ if(m % 2 == 0){ m /= 2; ans = "0" + ans; } else{ m--; m /= 2; ans = "1" + ans; } } return ans; } }
Submission Info
Submission Time | |
---|---|
Task | C - All Green |
User | tonq |
Language | Java8 (OpenJDK 1.8.0) |
Score | 300 |
Code Size | 1757 Byte |
Status | AC |
Exec Time | 112 ms |
Memory | 25428 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 300 / 300 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | a01, a02, a03, a04 |
All | a01, a02, a03, a04, b05, b06, b07, b08, b09, b10, b11, b12, b13, b14, b15, b16, b17, b18, b19, b20, b21, b22, b23, b24 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
a01 | AC | 93 ms | 23764 KB |
a02 | AC | 92 ms | 19796 KB |
a03 | AC | 93 ms | 19156 KB |
a04 | AC | 94 ms | 21204 KB |
b05 | AC | 94 ms | 19796 KB |
b06 | AC | 111 ms | 21460 KB |
b07 | AC | 110 ms | 21328 KB |
b08 | AC | 93 ms | 19024 KB |
b09 | AC | 93 ms | 23764 KB |
b10 | AC | 93 ms | 21716 KB |
b11 | AC | 93 ms | 19028 KB |
b12 | AC | 96 ms | 19284 KB |
b13 | AC | 99 ms | 21972 KB |
b14 | AC | 112 ms | 22868 KB |
b15 | AC | 110 ms | 23636 KB |
b16 | AC | 106 ms | 25428 KB |
b17 | AC | 112 ms | 23892 KB |
b18 | AC | 112 ms | 20820 KB |
b19 | AC | 111 ms | 21072 KB |
b20 | AC | 94 ms | 21844 KB |
b21 | AC | 99 ms | 21332 KB |
b22 | AC | 110 ms | 22868 KB |
b23 | AC | 102 ms | 22992 KB |
b24 | AC | 112 ms | 24784 KB |