oj.uz

Submission #31201

# Submission time Handle Problem Language Result Execution time Memory
31201 2017-08-13T13:40:09 Z chonka Divide and conquer (IZhO14_divide) C++
100 / 100
 79 ms 7108 KB 
#include<iostream>
#include<stdio.h>
using namespace std ;

#define MAXN 100007

int n ;
int x[ MAXN ] ;
int g[ MAXN ] ;
int d[ MAXN ] ;

long long pref[ MAXN ] ;

long long sm[ MAXN ] ;

class Tree {
    public :
    long long tr[ 3 * MAXN ] ;
    void init ( int where , int IL , int IR ) {
        if ( IL == IR ) {
            tr[ where ] = pref[ IL ] ;
            return ;
        }
        int mid = ( IL + IR ) / 2 ;
        init ( 2 * where , IL , mid ) ;
        init ( 2 * where + 1 , mid + 1 , IR ) ;
        tr[ where ] = max ( tr[ 2 * where ] , tr[ 2 * where + 1 ] ) ;
    }
    int query ( int where , int IL , int IR , int pos , long long sr ) {
        if ( tr[ where ] < sr ) { return 0 ; }
        if ( IR < pos ) { return 0 ; }
        if ( IL == IR ) { return IL ; }
        int mid = ( IL + IR ) / 2 ;
        int ret = query ( 2 * where + 1 , mid + 1 , IR , pos , sr ) ;
        if ( ret != 0 ) {
            return ret ;
        }
        return query ( 2 * where , IL , mid , pos , sr ) ;
    }
};
Tree w ;

void input ( ) {
    scanf ( "%d" , &n ) ;
    int i ;
    for ( i = 1 ; i <= n ; i ++ ) {
        scanf ( "%d%d%d" , &x[ i ] , &g[ i ] , &d[ i ] ) ;
        sm[ i ] = ( sm[ i - 1 ] + g[ i ] ) ;
        pref[ i ] = ( d[ i ] - x[ i ] + x[ i - 1 ] ) ;
        pref[ i ] += pref[ i - 1 ] ;
    }
    w.init ( 1 , 1 , n ) ;
}

void solve ( ) {
    int i ;
    long long sr ;
    long long ans = 0 ;
    for ( i = 1  ; i <= n ; i ++ ) {
        sr = pref[ i ] - d[ i ] ;
        int id = w.query ( 1 , 1 , n , i , sr ) ;
        if ( ans < ( sm[ id ] - sm[ i - 1 ] ) ) {
            ans = ( sm[ id ] - sm[ i - 1 ] ) ;
        }
    }
    printf ( "%lld\n" , ans ) ;
}


int main ( ) {
    input ( ) ;
    solve ( ) ;
    return 0 ;
}

Compilation message

divide.cpp: In function 'void input()':
divide.cpp:44:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ( "%d" , &n ) ;
                         ^
divide.cpp:47:58: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ( "%d%d%d" , &x[ i ] , &g[ i ] , &d[ i ] ) ;
                                                          ^

Subtask #1
17.0 / 17.0

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

Subtask #2
31.0 / 31.0

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

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 7108 KB Output is correct
2 Correct 0 ms 7108 KB Output is correct
3 Correct 3 ms 7108 KB Output is correct
4 Correct 23 ms 7108 KB Output is correct
5 Correct 23 ms 7108 KB Output is correct
6 Correct 39 ms 7108 KB Output is correct
7 Correct 33 ms 7108 KB Output is correct
8 Correct 43 ms 7108 KB Output is correct
9 Correct 36 ms 7108 KB Output is correct
10 Correct 46 ms 7108 KB Output is correct
11 Correct 76 ms 7108 KB Output is correct
12 Correct 79 ms 7108 KB Output is correct