Submission #320771

#TimeUsernameProblemLanguageResultExecution timeMemory
320771KWang31Divide and conquer (IZhO14_divide)Java
0 / 100
84 ms11828 KiB
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!
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...