oj.uz

Submission #320771

# Submission time Handle Problem Language Result Execution time Memory
320771 2020-11-09T20:00:13 Z KWang31 Divide and conquer (IZhO14_divide) Java 11
0 / 100
 84 ms 11828 KB 
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;
    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];
        x[0]=br.nextInt(); psag[1]=br.nextInt(); psae[1]=br.nextInt();
        
        for (int i = 1; i < N; i++) {
            x[i]=br.nextInt(); psag[i+1]=psag[i]+br.nextInt(); 
            psae[i+1]=psae[i]+br.nextInt()-(x[i]-x[i-1]);
        }
        //System.out.println(Arrays.toString(psae));
        arl=new ArrayList<>();
        arl.add(0); int t=0;
        for (int r = 1; r <= N; r++) {
            t=query(arl, psae[r]); 
            t=Math.min(r-1,t);
            MAX=Math.max(MAX, psag[r]-psag[t]);
            
            if(psae[r]<psae[arl.get(arl.size()-1)]){
                arl.add(r);
            }
            //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.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 11828 KB Output is correct
2 Incorrect 84 ms 11552 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 11828 KB Output is correct
2 Incorrect 84 ms 11552 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 11828 KB Output is correct
2 Incorrect 84 ms 11552 KB Output isn't correct
3 Halted 0 ms 0 KB -