Submission #74943597

---

Source Code Expand

import java.io.*;
import java.util.*;

public class Main {
    static long[] x;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] nm = br.readLine().split(" ");
        
        int n = Integer.parseInt(nm[0]);
        int m = Integer.parseInt(nm[1]);
        
        String[] dStr = br.readLine().split(" ");
        int[] d = new int[n];
        for(int i = 0; i < n; i++) d[i] = Integer.parseInt(dStr[i]);
        
        x = new long[m];
        if(m > 0) {
            String[] xStr = br.readLine().split(" ");
            for(int i = 0; i < m; i++) x[i] = Long.parseLong(xStr[i]);
            Arrays.sort(x);
        }
        
        int OFFSET = 50000;
        int SIZE = 100001;
        
        boolean[] dp = new boolean[SIZE];
        dp[OFFSET] = true;
        
        for(int i = 0; i < n; i++) {
            boolean[] next = new boolean[SIZE];
            
            for(int pos = 0; pos < SIZE; pos++) {
                if(!dp[pos]) continue;
                
                // skip
                next[pos] = true;
                
                // take
                int newPos = pos + d[i];
                if(newPos >= 0 && newPos < SIZE) {
                    long a = pos - OFFSET;
                    long b = newPos - OFFSET;
                    
                    if(!collision(a, b)) {
                        next[newPos] = true;
                    }
                }
            }
            
            dp = next;
        }
        
        long ans = Long.MIN_VALUE;
        for(int i = 0; i < SIZE; i++) {
            if(dp[i]) {
                ans = Math.max(ans, i - OFFSET);
            }
        }
        
        System.out.println(ans);
    }
    
    static boolean collision(long a, long b) {
        long l = Math.min(a, b);
        long r = Math.max(a, b);
        
        int idx = lowerBound(x, l);
        return idx < x.length && x[idx] <= r;
    }
    
    static int lowerBound(long[] a, long x) {
        int l = 0, r = a.length;
        while(l < r) {
            int mid = (l + r) / 2;
            if(a[mid] < x) l = mid + 1;
            else r = mid;
        }
        return l;
    }
}

Submission Info

Judge Result