oj.uz

Submission #801432

# Submission time Handle Problem Language Result Execution time Memory
801432 2023-08-02T06:02:29 Z Oz121 Bank (IZhO14_bank) Java 11
0 / 100
 222 ms 40176 KB 
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(0,0);

            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;
            }
        }

        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;
        }
    }
}

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 8268 KB Output is correct
2 Correct 52 ms 8132 KB Output is correct
3 Correct 52 ms 8476 KB Output is correct
4 Correct 58 ms 9804 KB Output is correct
5 Incorrect 222 ms 40176 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 8200 KB Output is correct
2 Incorrect 59 ms 8320 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 8268 KB Output is correct
2 Correct 52 ms 8132 KB Output is correct
3 Correct 52 ms 8476 KB Output is correct
4 Correct 58 ms 9804 KB Output is correct
5 Incorrect 222 ms 40176 KB Output isn't correct
6 Halted 0 ms 0 KB -