oj.uz

Submission #810859

# Submission time Handle Problem Language Result Execution time Memory
810859 2023-08-06T16:50:12 Z Username_taken12 Bank (IZhO14_bank) Java 11
19 / 100
 756 ms 87604 KB 
// Source: https://usaco.guide/general/io

import java.io.*;
import java.util.*;
import java.lang.Integer;

public class bank {
	public static void main(String[] args) throws IOException {
		BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);

		StringTokenizer st = new StringTokenizer(r.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		int[] ppl = new int[N+1];
		ppl[N]=0;
		int[] mon = new int[M];

		st= new StringTokenizer(r.readLine());
		for(int i = 0; i<N; i++)
			ppl[i]=Integer.parseInt(st.nextToken());
		st= new StringTokenizer(r.readLine());
		for(int j=0; j<M; j++)
			mon[j]=Integer.parseInt(st.nextToken());

		int[][] dp = new int[(1<<M)][2]; //ppl remaining
		for(int i=0; i<(1<<M); i++)
			dp[i]=new int[]{-1, Integer.MAX_VALUE};
		dp[0]=new int[]{0, ppl[0]};

		boolean pos=false;
		for(int i=0; i<M+1; i++){
			for(int j = 0; j<(1<<M); j++)
			{
				if(Integer.bitCount(j)!=i)
					continue;
				if(dp[j][0]==N){
					pos=true;
					break;
				}
				for(int k=0; k<M; k++)
				{
					if((j&(1<<k))!=0)
						continue;
					if(dp[j][1]==mon[k])
						dp[j+(1<<k)]=new int[]{dp[j][0]+1, ppl[dp[j][0]+1]};
					if(dp[j][1]>mon[k])
						dp[j+(1<<k)]=new int[]{dp[j][0], dp[j][1]-mon[k]};
				}
			}
			if(pos)
				break;
		}
		if(pos)
			pw.println("YES");
		else
			pw.println("NO");
		pw.close();
	}
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 8356 KB Output is correct
2 Correct 47 ms 8300 KB Output is correct
3 Correct 51 ms 8464 KB Output is correct
4 Correct 84 ms 12564 KB Output is correct
5 Correct 607 ms 87604 KB Output is correct
6 Correct 52 ms 8316 KB Output is correct
7 Correct 52 ms 8252 KB Output is correct
8 Correct 375 ms 87544 KB Output is correct
9 Correct 756 ms 87500 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 8476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 76 ms 12148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 8356 KB Output is correct
2 Correct 47 ms 8300 KB Output is correct
3 Correct 51 ms 8464 KB Output is correct
4 Correct 84 ms 12564 KB Output is correct
5 Correct 607 ms 87604 KB Output is correct
6 Correct 52 ms 8316 KB Output is correct
7 Correct 52 ms 8252 KB Output is correct
8 Correct 375 ms 87544 KB Output is correct
9 Correct 756 ms 87500 KB Output is correct
10 Incorrect 53 ms 8476 KB Output isn't correct
11 Halted 0 ms 0 KB -