Submission #638766

#	Time	Username	Problem	Language	Result	Execution time	Memory
638766		morasha3	Rainy Markets (CCO22_day1problem2)	C++17	5 / 25	476 ms	98592 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef   double ld;
const ll mod=1e9+7;
#define endl '\n'

int32_t main()
{
    //freopen("jumping.in","r",stdin);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin>>n;
    ll arr[n],a[n];
    for(int i=0; i<n; i++)
    {
        cin>>arr[i];
        a[i]=arr[i];
    }
    vector<ll>v,b;
    for(int i=0; i<n-1; i++)
    {
        ll x;
        cin>>x;
        v.push_back(x);
    }

    for(int i=0; i<n-1; i++)
    {
        ll x;
        cin>>x;
        b.push_back(x);
    }
    bool f=1;
    ll cnt=0;
    for(int i=0; i<n-1; i++)
    {
        ll o=v[i];
        o-=arr[i]-cnt;
        cnt=0;
        if(o>0)
        {
            o-=b[i];
            if(o>0)
            {
                ll u=o;
                o-=arr[i+1];
                if(o>0)
                {
                    f=0;
                    break;
                }
                cnt=u;
            }
        }
    }
    if(f==0)
    {
        cout<<"NO";
    }
    else
    {
        cnt=0;
        ll ans=0;
        cout<<"YES"<<endl;
        cnt=0;
        ll ans1[n-1],ans2[n-1],ans3[n-1];
        for(int i=0; i<n-1; i++)
        {
            ll o=v[i];
            o-=arr[i];
            ans1[i]=(min(arr[i],v[i]));
            arr[i]-=min(arr[i],v[i]);
            if(o>0)
            {
                v[i]=o;
                o-=b[i];
                ans2[i]=(min(b[i],v[i]));
                if(o>0)
                {
                    v[i]=o;
                    ans3[i]=(v[i]);
                    arr[i+1]-=v[i];
                }
                else
                    ans3[i]=(0);
            }
            else
            {
                ans2[i]=(0);
                ans3[i]=(0);
            }
        }
        for(int i=0; i<n-1; i++)
        {
            if(arr[i]>0)
            {
                ll o=min(ans2[i],arr[i]);
                ans2[i]-=o;
                ans1[i]+=o;
                if(arr[i]>0)
                {
                    ll o=min(arr[i+1]+arr[i],a[i+1]);
                    o=o-arr[i+1];
                    arr[i+1]+=o;
                    ll u=0;
                    if(i==0)
                    u=min({o,ans3[i],a[i]-ans1[i]});
                    else u=min({o,ans3[i],(a[i]-ans3[i-1])-ans1[i]});
                    ans1[i]+=u;
                    ans3[i]-=u;
                    arr[i]-=o;

                }
            }
        }
        for(int i=n-2; i>=0; i--)
        {
            if(arr[i+1]>0)
            {
                ll o=min(ans2[i],arr[i+1]);
                ans2[i]-=o;
                ans3[i]+=o;
                arr[i+1]-=o;
                if(arr[i+1]>0)
                {
                    o=min(arr[i]+arr[i+1],a[i]);
                    o=o-arr[i];
                    arr[i]+=o;
                    ll u=0;
                    if(i!=n-2)
                     u=min({o,ans1[i],(a[i+1]-ans1[i+1])-ans3[i]});
                    else  u=min({o,ans1[i],(a[i+1])-ans3[i]});
                    ans3[i]+=u;
                    ans1[i]-=u;
                }
            }
        }
        for(int i=0; i<n-1; i++)
        {
            ans+=ans2[i];
        }
        cout<<ans<<endl;
        for(int i=0; i<n-1; i++)
        {
            cout<<ans1[i]<<" "<<ans2[i]<<" "<<ans3[i]<<endl;
        }
    }


    return 0;

}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 6
• Subtask 4: 0 / 9