Cod sursa(job #3258339)

Utilizator LORDENVraja Luca LORDEN Data 22 noiembrie 2024 08:41:48
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <fstream>
#include <deque>

using namespace std ;

ifstream cin ("buline.in") ;
ofstream cout ("buline.out") ;

int n, dp[400005] ;

///to-do : sotron, peri, joctv, buline

int main()
{

    int x, ans, st = 0, lmax = 0 ;
    bool color ;

    cin >> n ;

    for (int i = 1 ; i <= n ; i ++)
    {

        cin >> x >> color ;

        if (!color)
            dp[i] -= x ;

        else
            dp[i] += x ;

        dp[i + n] = dp[i] ;

    }

    deque < int > dq ;
    dq.push_back (1) ;

    for (int i = 2 ; i <= 2 * n ; i ++)
    {

        dp[i] += dp[i - 1] ;

        while (!dq.empty() && i - dq.front() > n)
            dq.pop_front() ;

        if (dp[i] - dp[dq.front()] > ans)
        {

            ans = dp[i] - dp[dq.front()] ;
            st = dq.front() + 1 ;
            lmax = i - dq.front() ;

        }

        while (!dq.empty() && dp[dq.back()] > dp[i])
            dq.pop_back() ;

        dq.push_back (i) ;

    }

    cout << ans << ' ' << st << ' ' << lmax ;

    return 0 ;

}