oj.uz

답안 #17465

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
17465 2015-12-18T10:07:19 Z AZE_XeRoX 금 캐기 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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