Submission #31201

#	Time	Username	Problem	Language	Result	Execution time	Memory
31201		chonka	Divide and conquer (IZhO14_divide)	C++98	100 / 100	79 ms	7108 KiB

divide

#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 (stderr)

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 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52