oj.uz

Submission #17465

# Submission time Handle Problem Language Result Execution time Memory
17465 2015-12-18T10:07:19 Z AZE_XeRoX Divide and conquer (IZhO14_divide) C++
100 / 100
 146 ms 4720 KB 
#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4716 KB Output is correct
2 Correct 0 ms 4716 KB Output is correct
3 Correct 0 ms 4716 KB Output is correct
4 Correct 0 ms 4716 KB Output is correct
5 Correct 0 ms 4720 KB Output is correct
6 Correct 0 ms 4712 KB Output is correct
7 Correct 0 ms 4712 KB Output is correct
8 Correct 0 ms 4720 KB Output is correct
9 Correct 0 ms 4716 KB Output is correct
10 Correct 0 ms 4712 KB Output is correct
11 Correct 0 ms 4720 KB Output is correct
12 Correct 0 ms 4720 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4712 KB Output is correct
2 Correct 0 ms 4716 KB Output is correct
3 Correct 0 ms 4716 KB Output is correct
4 Correct 1 ms 4716 KB Output is correct
5 Correct 2 ms 4720 KB Output is correct
6 Correct 0 ms 4716 KB Output is correct
7 Correct 1 ms 4716 KB Output is correct
8 Correct 1 ms 4712 KB Output is correct
9 Correct 0 ms 4712 KB Output is correct
10 Correct 0 ms 4712 KB Output is correct
11 Correct 8 ms 4716 KB Output is correct
12 Correct 8 ms 4716 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4720 KB Output is correct
2 Correct 12 ms 4720 KB Output is correct
3 Correct 11 ms 4712 KB Output is correct
4 Correct 62 ms 4716 KB Output is correct
5 Correct 69 ms 4712 KB Output is correct
6 Correct 146 ms 4712 KB Output is correct
7 Correct 105 ms 4716 KB Output is correct
8 Correct 115 ms 4716 KB Output is correct
9 Correct 120 ms 4712 KB Output is correct
10 Correct 126 ms 4716 KB Output is correct
11 Correct 146 ms 4720 KB Output is correct
12 Correct 122 ms 4716 KB Output is correct