Cod sursa(job #3376481)

Utilizator alex.iovita.23@gmail.comIovita Alexandru [email protected] Data 17 noiembrie 2026 21:54:41
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.3 kb
#include<bits/stdc++.h>
#define int long long

using namespace std;

ifstream fin("buline.in");
ofstream fout("buline.out");

int n , v[400001] , sp[400001];

signed main(){
    fin >> n;
    for(int i = 1 ; i <= n ; i++){
        int x , tip; fin >> x >> tip;
        if(tip == 0) v[i] -= x;
        else v[i] = x;
    }
    for(int i = 1 ; i <= 2 * n ; i++) sp[i] = sp[i - 1] + v[(i - 1) % n + 1];
    int sum = -2e18 , st = 1 , dr = 1;
    deque<int> dq;
    dq.push_back(0);
    for(int i = 1 ; i <= 2 * n ; i++){
        while(!dq.empty() && dq.front() < i - n) dq.pop_front();
        if(!dq.empty()){
            int j = dq.front();
            int cur_sum = sp[i] - sp[j];
            int cur_st = (j % n) + 1;
            int cur_dr = i - j;
            if(cur_sum > sum){
                sum = cur_sum;
                st = cur_st;
                dr = cur_dr;
            }
            else if(cur_sum == sum){
                if(cur_st < st){
                    st = cur_st;
                    dr = cur_dr;
                }
                else if(cur_st == st && cur_dr < dr) dr = cur_dr;
            }
        }
        while(!dq.empty() && sp[dq.back()] >= sp[i]) dq.pop_back();
        dq.push_back(i);
    }
    fout << sum << " " << st << " " << dr;
    return 0;
}