Cod sursa(job #3340887)

Utilizator ligmasigmaolimpiadaVlad Bratucu ligmasigmaolimpiada Data 16 februarie 2026 22:31:12
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.92 kb
#include <fstream>
#include <vector>

using namespace std;

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

int main()
{
    int N;
    fin>>N;
    vector<long long> v(N+1);
    for(int i=1;i<=N;i++){
        long long x;
        int c;
        fin>>x>>c;
        if(c==0) v[i]=-x;
        else v[i]=x;
    }
    long long bestSum=v[1], currSum=v[1];
    int bestStart=1, bestLen=1;
    int currStart=1;
    for(int i=2;i<=N;i++){
        if(currSum+v[i]<v[i]){
            currSum=v[i];
            currStart=i;
        }else{
            currSum+=v[i];
        }
        int currLen=i-currStart+1;
        if(currSum>bestSum ||(currSum==bestSum &&(currStart<bestStart ||(currStart==bestStart && currLen<bestLen)))){
            bestSum=currSum;
            bestStart=currStart;
            bestLen=currLen;
        }
    }
    long long total=0;
    for(int i=1;i<=N;i++){
        total+=v[i];
    }
    long long minSum=v[1], currMin=v[1];
    int minStart=1, minLen=1;
    int currMinStart=1;
    for(int i=2;i<=N;i++){
        if(currMin+v[i]>v[i]){
            currMin=v[i];
            currMinStart=i;
        }else{
            currMin+=v[i];
        }
        int currLen=i-currMinStart+1;
        if(currMin<minSum ||(currMin==minSum &&(currMinStart<minStart ||(currMinStart==minStart && currLen<minLen)))){
            minSum=currMin;
            minStart=currMinStart;
            minLen=currLen;
        }
    }
    if(minLen!=N){
        long long circSum=total-minSum;
        int circStart=minStart+minLen;
        if(circStart>N) circStart-=N;
        int circLen=N-minLen;
        if(circSum>bestSum ||(circSum==bestSum &&(circStart<bestStart ||(circStart==bestStart && circLen<bestLen)))){
            bestSum=circSum;
            bestStart=circStart;
            bestLen=circLen;
        }
    }
    fout<<bestSum<<' '<<bestStart<<' '<<bestLen;
    return 0;
}