Submission #1207860

#TimeUsernameProblemLanguageResultExecution timeMemory
1207860uranium235Bank (IZhO14_bank)Java
19 / 100
145 ms20396 KiB
//package ojuz; import java.io.*; import java.util.*; public class bank { public static void main(String[] args) throws IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); String[] first = reader.readLine().split(" "); int n = Integer.parseInt(first[0]), m = Integer.parseInt(first[1]); int[] salary = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray(); int[] notes = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray(); int[] dp = new int[1 << m]; Arrays.fill(dp, -1); dp[0] = 0; int[] pd = new int[1 << m]; for (int i = 1; i < (1 << m); i++) { for (int j = i; j > 0; j -= j & -j) { int idx = Integer.numberOfTrailingZeros(j); if (dp[i ^ j] == -1) continue; int cmp = Integer.compare(pd[i ^ j] + notes[idx], salary[dp[i ^ j]]); int newDp = dp[i ^ j], newPd = pd[i ^ j]; if (cmp == 0) { // adding this note completes a persons salary newDp++; newPd = 0; } else if (cmp < 0) { // adding this note partially completes a persons salary newPd += notes[idx]; } // same prefix done, maximize part done if (newDp == dp[i]) pd[i] = Math.max(pd[i], newPd); // greater prefix done else if (newDp > dp[i]) { dp[i] = newDp; pd[i] = newPd; } } if (dp[i] == n) { System.out.println("YES"); return; } } System.out.println("NO"); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...