Submission #320780

#	Time	Username	Problem	Language	Result	Execution time	Memory
320780		KWang31	Divide and conquer (IZhO14_divide)	Java	0 / 100	86 ms	11444 KiB

divide

import java.io.*; import java.util.*;
public class divide{
  static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        
    } 
    static int N;
    static long MAX=0;
    static ArrayList<Integer> arl;
    static long[] psae, psag,e;
    public static void main(String[] args){
        FastReader br=new FastReader();
        N=br.nextInt(); 
        psae=new long[N+1]; psag=new long[N+1];
        int[] x=new int[N+1]; e=new long[N+1];
        x[1]=br.nextInt(); psag[1]=br.nextInt(); 
        psae[1]=-x[1];
        if(N==1){System.out.println(psag[1]);return;}
        e[1]=psae[2]=br.nextInt(); psae[2]+=x[1] ;
        
        for (int i = 2; i <= N; i++) {
            x[i]=br.nextInt(); psae[i]-=x[i];
            psag[i]=psag[i-1]+br.nextInt(); 
            e[i]=br.nextInt();
            if(i<N){psae[i+1]=psae[i]+e[i]+x[i];}
        }
        /*
        System.out.println(Arrays.toString(psae));
        System.out.println(Arrays.toString(e));
        System.out.println(Arrays.toString(psag));*/
        arl=new ArrayList<>();//A set of indices to check in ascending order
        arl.add(0); int t=0;
        for (int r = 1; r <= N; r++) {
            //System.out.println(psae[r]+e[r]);
            if(psae[r]<psae[arl.get(arl.size()-1)]){
                arl.add(r);
            }
            t=query(arl, psae[r]+e[r]); 
            t=Math.min(r-1,t);
            MAX=Math.max(MAX, psag[r]-psag[t]);
            
            
            //System.out.println(arl);
        }
        System.out.println(MAX);
    }
    
     
     public static int query(ArrayList<Integer> arl, long q){//Finding the best element in this monotone array
         
         int l=0; int r=arl.size()-1;
         if(psae[arl.get(r)]>q){//Nothing works
             return N;
         }
         while(l<r){
             int mid=(l+r)/2;
             if(q>=psae[arl.get(mid)]){
                 r=mid;
             }else{
                 l=mid+1;//1,...,mid can't be used
             }
         }
         return arl.get(l);
    }
}
//Debugging:
//Are you sure your algorithm is correct?
//Bounds: long
//Special cases: n=0,1?
//Make sure you remove your debugging code before you submit!

• Subtask 1: 0 / 17
• Subtask 2: 0 / 31
• Subtask 3: 0 / 52