Submission #713717

#	Time	Username	Problem	Language	Result	Execution time	Memory
713717		mtxas	Potatoes and fertilizers (LMIO19_bulves)	C++14	34 / 100	114 ms	31848 KiB

bulves

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define int long long
#define DISABLE_PRINTF
#ifdef DISABLE_PRINTF
#define printf(...)
#endif // DISABLE_PRINTF
using namespace std;
void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1), b(n + 1);
    for(int i = 1; i <= n; ++i)
    {
        cin >> a[i] >> b[i];
    }
    int A = 0;
    int B = 0;
    for(int i = 1; i <= n; ++i)
    {
        A += a[i], B += b[i];
    }
    if(A == B)
    {
        /// solve it
        int ans = 0;
        int aid = 1, bid = 1;
        for(; bid <= n; ++bid)
        {
            for(; b[bid] > 0; ++aid)
            {
                int take = min(a[aid], b[bid]);
                b[bid] -= take;
                a[aid] -= take;
                ans += take * abs(bid - aid);
                if(b[bid] == 0)
                {
                    break;
                }
            }
        }
        cout << ans;
    }
    else if(A == B + 1)
    {
        vector<int> pref(n + 1), suff(n + 2);
        vector<int> prefLastDelta(n + 1), suffLastDelta(n + 2);
        vector<int> acopy = a, bcopy = b;
        /// calc pref
        int bid = 1;
        for(int i = 1; i <= n; ++i)
        {
            pref[i] = pref[i - 1];
//            prefLastDelta[i] = prefLastDelta[i - 1];
            for(; a[i] > 0; bid += (b[bid] == 0) )
            {
                if(bid == n + 1) break;
                int take = min(a[i], b[bid]);
                a[i] -= take;
                b[bid] -= take;
                pref[i] += abs(i - bid) * take;
                if(take > 0)
                {
                    prefLastDelta[i] = (abs(i - bid));
                }
            }
        }
        a = acopy;
        b = bcopy;
        bid = n;
        /// calc suff
        for(int i = n; i >= 1; --i)
        {
            suff[i] = suff[i + 1];
//            suffLastDelta[i] = suffLastDelta[i + 1];
            for(; a[i] > 0; bid -= (b[bid] == 0) )
            {
                if(bid == 0) break;
                int take = min(a[i], b[bid]);
                a[i] -= take;
                b[bid] -= take;
                suff[i] += abs(i - bid) * take;
                if(take > 0)
                {
                    suffLastDelta[i] = (abs(i - bid));
                }
            }
        }
        a = acopy;
        b = bcopy;
        int ans = min(suff[1], pref[n]);
        printf("suff[1] = %lld\npref[n] = %lld\n", suff[1], pref[n]);
        int ferCnt = 0;
        for(int i = 1; i <= n; ++i)
        {
            ferCnt += a[i];
            if(ferCnt == 0 || ferCnt == A) continue;
            printf("i = %d\n", i);
            ans = min(ans, pref[i] + suff[i + 1] -
                      max(prefLastDelta[i],
                          suffLastDelta[i + 1]));
        }
        cerr << "the case" << endl;
        cout << ans << '\n';
    }
}
signed main()
{
#ifdef EVAL
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);
#else
    freopen("input_00.txt", "r", stdin);
#endif // EVAL

    solve();
}

• Subtask 1: 24 / 24
• Subtask 2: 10 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 36