Submission #489537

#	Time	Username	Problem	Language	Result	Execution time	Memory
489537		yungyao	Remittance (JOI19_remittance)	C++17	0 / 100	20 ms	332 KiB

remittance

using namespace std;
#pragma GCC optimize ("Ofast")
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#include <stack>
#include <set>
#include <map>

typedef long long LL;
typedef pair<int,int> pii;
#define iter(x) x.begin(),x.end()
#define pb push_back
#define mkp make_pair
#define F first
#define S second
#define REP(n) for (int __=n;__--;)
#define REP0(i,n) for (int i=0;i<n;++i)
#define REP1(i,n) for (int i=1;i<=n;++i)

const int maxn = 1e6+10,mod = 0;
const LL inf = 0;

int n;
int a[maxn],b[maxn];
int op[maxn];

bool sol(int l,int s){
    if (l == n){
        REP0(i,n) if (a[i] - op[i] * 2 + op[(i+n-1)%n] != b[i]) return false;
        return true;
    }

    for (int i = 0;i<=s;++i){
        op[l] = i;
        sol(l+1,s-i);
        if (sol(l+1,s - i)) return true;
    }
    return false;
}

void solve(){


    cin >> n;
    int asum = 0,bsum = 0;
    REP0(i,n) cin >> a[i] >> b[i], asum += a[i], bsum += b[i];
    bool s = true;
    REP0(i,n) s &= a[i] == b[i];
    if (s){
        cout << "Yes\n";
        return;
    }
    else if (asum <= bsum){
        cout << "No\n";
        return;
    }

    cout << (sol(0,asum - bsum) ? "Yes\n" : "No\n");
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    solve();

    return 0;
}

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