Cod sursa(job #3365468)

Utilizator andrei_obrejaAndrei Obreja andrei_obreja Data 21 septembrie 2026 11:35:15
Problema Ciclu Eulerian Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.84 kb
#include <bits/stdc++.h>
#define int long long int
const int lim = 2000000001;
using namespace std;
ifstream fin("summax.in");
ofstream fout ("summax.out");

void cer1(int n, vector<pair<int,int>> &dp1)
{
    vector<pair<int,int>> dp2;
    dp2.resize(n + 1);
    int x;
    fin >> x;
    dp1[1].first = x;
    dp1[1].second = 1;
    for(int i = 2; i <= n; i++)
    {
        for(int j = 1; j<=i; j++)
        {
            int x;
            fin >> x;
            if(j == 1)
            {
                dp2[j].first = dp1[j].first + x;
                dp2[j].second = dp1[j].second;
            }
            else if(j == i)
            {
                dp2[j].first = dp1[j - 1].first + x;
                dp2[j].second = dp1[j - 1].second;
            }
            else
            {
                if(dp1[j - 1].first > dp1[j].first)
                    dp2[j].first = dp1[j - 1].first + x,dp2[j].second =min(lim,dp1[j - 1].second) ;
                if(dp1[j - 1].first < dp1[j].first)
                    dp2[j].first = dp1[j].first + x,dp2[j].second = min(lim,dp1[j].second);
                if(dp1[j - 1].first == dp1[j].first)
                    dp2[j].first = dp1[j].first + x,dp2[j].second = min(lim, dp1[j].second + dp1[j - 1].second);
            }
        }
        dp1 = dp2;
    }
}
signed main()
{
    int cerinta ;
    fin >> cerinta;
    int n, st, dr;

    fin >> n >> st >> dr;
    vector<pair<int,int>> dp(n + 1);
    if(cerinta == 1)
    {
        cer1(n, dp);
        int ans =0;
        int maxsum = 0;
        for(int j= 1; j <= n; j++)
        {
            if(dp[j].first > maxsum)
                maxsum = dp[j].first, ans = 0;
            if(maxsum == dp[j].first)
                ans = min(lim, ans + dp[j].second);
        }
        fout << ans << '\n';
    }
    return 0;
}