Submission #17465

#	Time	Username	Problem	Language	Result	Execution time	Memory
17465		AZE_XeRoX	Divide and conquer (IZhO14_divide)	C++98	100 / 100	146 ms	4720 KiB

divide

#include <iostream>
#include <cmath>
#include <iomanip>
#include <algorithm>

#define intt long long int
#define MAXN 100001
using namespace std;
 
intt n;

int main()
{
   
   

   
    long long x[MAXN], g[MAXN], d[MAXN], p[MAXN];
  
    cin >> n ;   
 
   
    for (intt i=1; i<=n; i++) {

        cin >> x[i] >> g[i] >> d[i] ;
       
       
        g[i] += g[i-1];
       
        d[i] += d[i-1];
         
        p[i] = d[i] - x[i];
   
    }
    
    for ( intt i = n - 1 ; i ; i--) {
        
        p[i] = max ( p[i] , p[i+1] ) ;
 
    }
    
    intt r = 0;
    
    for ( intt i = 1 ; i <= n; i ++ )
     {
    
        intt s , e ;
       
        s = i ; 
        
        e = n ;
        
        while (s != e) 
        
        {
       
            intt  m ;
            
          m = ( s + e + 1 ) / 2 ;
       
            if( d[i-1] - x[i] <= p[m] ) s = m;
       
            else e = m-1;
        }
       
        if( d[i-1] - x[i] <= p[s] )

       
            r = max ( r , g[s] - g[i-1] ) ;
     
    }
    
    cout << r << endl;
    
    return 0;
}

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