Naive O(N^2) DP solution

GuardiansoftheLunaticsVol2.java

import java.util.*;
import java.io.*;
public class GuardiansoftheLunaticsVol2 {
    
    
    
    /************************ SOLUTION STARTS HERE ************************/
    
    static long memo[];
    static long pref[];
    static int k , n;
    static final long INF = (long) 1e18;
    static long getCost(int L , int R) {
        return pref[R] - pref[L - 1];
    }
    static long rec(int idx) {
        if(idx == 0)
            return 0;
        
        if(memo[idx] != -1)
            return memo[idx];
        
        long min = INF;
        for(int start = Math.max(1 , idx - k + 1); start <= idx && start + k - 1 <= n; start++)
            min = Math.min(min , getCost(start, start + k - 1) + rec(start - 1));
        
        return memo[idx] = min;
    }
    
    private static void solve() {
        
        
        int T = nextInt();
        while(T-->0) {
            n = nextInt();
            int q = nextInt();
            int p[] = nextIntArrayOneBased(n);
            pref = new long[n + 1];
            for(int i = 1; i <= n; i++)
                pref[i] = p[i] + pref[i - 1];
            
            while(q-->0) {
                memo = new long[n + 1];
                Arrays.fill(memo, -1);
                k = nextInt();
                println(rec(n));
            }
        }
        
        
        
    }
    
    
    
    /************************ SOLUTION ENDS HERE ************************/
    
    
    
    
    
    /************************ TEMPLATE STARTS HERE **********************/
    
    public static void main(String[] args) throws IOException {
        reader = new BufferedReader(new InputStreamReader(System.in));
        writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)), false);
        st     = null;
        solve();
        reader.close();
        writer.close();
    }
    
    static BufferedReader reader;
    static PrintWriter    writer;
    static StringTokenizer st;
    
    static String next()
    {while(st == null || !st.hasMoreTokens()){try{String line = reader.readLine();if(line == null){return null;}            
    st = new StringTokenizer(line);}catch (Exception e){throw new RuntimeException();}}return st.nextToken();}
    static String nextLine()  {String s=null;try{s=reader.readLine();}catch(IOException e){e.printStackTrace();}return s;}             
    static int    nextInt()   {return Integer.parseInt(next());}
    static long   nextLong()  {return Long.parseLong(next());}     
    static double nextDouble(){return Double.parseDouble(next());}
    static char   nextChar()  {return next().charAt(0);}
    static int[]  nextIntArray(int n)         {int[] a= new int[n];   int i=0;while(i<n){a[i++]=nextInt();}  return a;}
    static long[] nextLongArray(int n)        {long[]a= new long[n];  int i=0;while(i<n){a[i++]=nextLong();} return a;}    
    static int[]  nextIntArrayOneBased(int n) {int[] a= new int[n+1]; int i=1;while(i<=n){a[i++]=nextInt();} return a;}            
    static long[] nextLongArrayOneBased(int n){long[]a= new long[n+1];int i=1;while(i<=n){a[i++]=nextLong();}return a;}            
    static void   print(Object o)  { writer.print(o);  }
    static void   println(Object o){ writer.println(o);}
    
    /************************ TEMPLATE ENDS HERE ************************/
    
}