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!
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
86 ms |
11444 KB |
Output is correct |
| 2 |
Incorrect |
83 ms |
11160 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
86 ms |
11444 KB |
Output is correct |
| 2 |
Incorrect |
83 ms |
11160 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
86 ms |
11444 KB |
Output is correct |
| 2 |
Incorrect |
83 ms |
11160 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
