제출 #811679

#제출 시각아이디문제언어결과실행 시간메모리
811679Oz121은행 (IZhO14_bank)Java
0 / 100
56 ms8456 KiB
import java.io.*; import java.util.*; public class bank { public static void main(String[] args) throws IOException { BufferedReader scan = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer l1 = new StringTokenizer(scan.readLine()); int num = Integer.parseInt(l1.nextToken()); int m = Integer.parseInt(l1.nextToken()); int[] a = new int[num]; StringTokenizer st1 = new StringTokenizer(scan.readLine()); for (int i = 0;i<num;i++) { a[i] = Integer.parseInt(st1.nextToken()); } int[] b = new int[m]; StringTokenizer st2 = new StringTokenizer(scan.readLine()); for (int i = 0;i<m;i++) { b[i] = Integer.parseInt(st2.nextToken()); } Pair[] dp = new Pair[1<<m]; //Stores first i people we can satisfy and the leftover dp[0] = new Pair(-1,0); for (int i = 1;i<1<<m;i++) { dp[i] = new Pair(-2,-1); for (int j = 0;j<m;j++) { if ((i&(1<<j))==0) continue; Pair prev = dp[i&(~(1<<j))]; if (prev.first==num-1) continue; if (prev.left+b[j]==a[prev.first+1]) { dp[i].first = prev.first+1; dp[i].left = 0; } else if (prev.left+b[j]<a[prev.first+1]) { dp[i].first = prev.first; dp[i].left = prev.left+b[j]; } } } boolean ans = false; for (int i = 0;i<1<<m;i++) { if (dp[i].first == num - 1) { ans = true; break; } } if (ans) System.out.println("YES"); else System.out.println("NO"); } public static class Pair { int first; int left; public Pair (int first, int left) { this.first = first; this.left = left; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...