Submission #1207861

#TimeUsernameProblemLanguageResultExecution timeMemory
1207861uranium235은행 (IZhO14_bank)Java
100 / 100
178 ms20432 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 k = j & -j; int idx = Integer.numberOfTrailingZeros(k); if (dp[i ^ k] == -1) continue; int cmp = Integer.compare(pd[i ^ k] + notes[idx], salary[dp[i ^ k]]); int newDp = dp[i ^ k], newPd = pd[i ^ k]; 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...