Submission #672237

#	Time	Username	Problem	Language	Result	Execution time	Memory
672237		Hanksburger	Remittance (JOI19_remittance)	C++17	100 / 100	219 ms	36456 KiB

remittance

#include <bits/stdc++.h>
using namespace std;
long long a[1000005], b[1000005];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n, l=0, r=2e9;
    cin >> n;
    for (long long i=1; i<=n; i++)
        cin >> a[i] >> b[i];
    while (l<r)
    {
        long long m=(l+r)/2;
        for (long long i=n; i>=1; i--)
        {
            m=m*2-a[i]+b[i];
            if (m<0 || m>2e9)
                break;
        }
        if (m<(l+r)/2)
            l=(l+r)/2+1;
        else
            r=(l+r)/2;
    }
    for (long long i=n; i>=1; i--)
    {
        l=l*2-a[i]+b[i];
        if (l<0 || l>2e9)
            break;
    }
    bool ok=0;
    if (l==r)
    {
        for (long long i=1; i<=n; i++)
        {
            if (b[i])
            {
                ok=1;
                break;
            }
        }
        bool all0=1;
        for (long long i=1; i<=n; i++)
        {
            if (a[i])
            {
                all0=0;
                break;
            }
        }
        if (all0)
            ok=1;
    }
    cout << (ok?"Yes":"No");
}

• Subtask 1: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 45 / 45