oj.uz

Submission #320813

# Submission time Handle Problem Language Result Execution time Memory
320813 2020-11-10T01:56:20 Z KWang31 Divide and conquer (IZhO14_divide) Java 11
100 / 100
 520 ms 45680 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,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(); 
        
        if(N==1){System.out.println(psag[1]);return;}
        e[1]=br.nextInt(); 
        
        for (int i = 2; i <= N; i++) {
            x[i]=br.nextInt(); 
            psag[i]=psag[i-1]+br.nextInt(); 
            e[i]=br.nextInt();
            
        }
        long sum=0; psae[1]=-x[1];
        for (int i =2; i <=N; i++) {
            sum+=e[i-1]; psae[i]=sum-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
        int t=0;
        for (int r = 1; r <= N; r++) {
            //System.out.println(psae[r]+e[r]);
            if(arl.isEmpty() || psae[r]<psae[arl.get(arl.size()-1)]){
                arl.add(r);
            }
            t=query(arl, psae[r]+e[r]); 
            
            MAX=Math.max(MAX, psag[r]-psag[t-1]);
            //System.out.println(r+" "+t+" "+arl+(psae[r]+e[r]));
        }
        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
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 11588 KB Output is correct
2 Correct 85 ms 11572 KB Output is correct
3 Correct 85 ms 11312 KB Output is correct
4 Correct 84 ms 11324 KB Output is correct
5 Correct 90 ms 11360 KB Output is correct
6 Correct 101 ms 11684 KB Output is correct
7 Correct 87 ms 11488 KB Output is correct
8 Correct 86 ms 11440 KB Output is correct
9 Correct 89 ms 11608 KB Output is correct
10 Correct 86 ms 11436 KB Output is correct
11 Correct 96 ms 11680 KB Output is correct
12 Correct 96 ms 11364 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 11588 KB Output is correct
2 Correct 85 ms 11572 KB Output is correct
3 Correct 85 ms 11312 KB Output is correct
4 Correct 84 ms 11324 KB Output is correct
5 Correct 90 ms 11360 KB Output is correct
6 Correct 101 ms 11684 KB Output is correct
7 Correct 87 ms 11488 KB Output is correct
8 Correct 86 ms 11440 KB Output is correct
9 Correct 89 ms 11608 KB Output is correct
10 Correct 86 ms 11436 KB Output is correct
11 Correct 96 ms 11680 KB Output is correct
12 Correct 96 ms 11364 KB Output is correct
13 Correct 94 ms 11588 KB Output is correct
14 Correct 95 ms 11476 KB Output is correct
15 Correct 125 ms 12020 KB Output is correct
16 Correct 122 ms 12000 KB Output is correct
17 Correct 130 ms 12192 KB Output is correct
18 Correct 140 ms 12212 KB Output is correct
19 Correct 130 ms 12228 KB Output is correct
20 Correct 122 ms 11976 KB Output is correct
21 Correct 153 ms 12432 KB Output is correct
22 Correct 153 ms 12768 KB Output is correct
23 Correct 196 ms 16608 KB Output is correct
24 Correct 217 ms 16612 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 11588 KB Output is correct
2 Correct 85 ms 11572 KB Output is correct
3 Correct 85 ms 11312 KB Output is correct
4 Correct 84 ms 11324 KB Output is correct
5 Correct 90 ms 11360 KB Output is correct
6 Correct 101 ms 11684 KB Output is correct
7 Correct 87 ms 11488 KB Output is correct
8 Correct 86 ms 11440 KB Output is correct
9 Correct 89 ms 11608 KB Output is correct
10 Correct 86 ms 11436 KB Output is correct
11 Correct 96 ms 11680 KB Output is correct
12 Correct 96 ms 11364 KB Output is correct
13 Correct 94 ms 11588 KB Output is correct
14 Correct 95 ms 11476 KB Output is correct
15 Correct 125 ms 12020 KB Output is correct
16 Correct 122 ms 12000 KB Output is correct
17 Correct 130 ms 12192 KB Output is correct
18 Correct 140 ms 12212 KB Output is correct
19 Correct 130 ms 12228 KB Output is correct
20 Correct 122 ms 11976 KB Output is correct
21 Correct 153 ms 12432 KB Output is correct
22 Correct 153 ms 12768 KB Output is correct
23 Correct 196 ms 16608 KB Output is correct
24 Correct 217 ms 16612 KB Output is correct
25 Correct 158 ms 13520 KB Output is correct
26 Correct 215 ms 17244 KB Output is correct
27 Correct 213 ms 17824 KB Output is correct
28 Correct 380 ms 31796 KB Output is correct
29 Correct 335 ms 32208 KB Output is correct
30 Correct 429 ms 45680 KB Output is correct
31 Correct 430 ms 44560 KB Output is correct
32 Correct 412 ms 44280 KB Output is correct
33 Correct 468 ms 44360 KB Output is correct
34 Correct 490 ms 44716 KB Output is correct
35 Correct 520 ms 45224 KB Output is correct
36 Correct 493 ms 45644 KB Output is correct