Submission #741466

#	Time	Username	Problem	Language	Result	Execution time	Memory
741466		myrcella	Remittance (JOI19_remittance)	C++17	0 / 100	1 ms	340 KiB

remittance

//by szh
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

const int maxn = 22;

int n;
int a[maxn],b[maxn],dif[maxn];
int dp[(1<<maxn)];
bool hmm[(1<<maxn)];

bool check(int mask) {
	bool tmp[maxn];
	memset(tmp,false,sizeof(tmp));
	rep(i,0,n) if ((mask>>i)&1) tmp[i] = true;
	rep(i,0,n) {
		ll cur = 0;
		bool ok = true;
		for (int j=i;j>=0 and ok;j--) {
			cur*=2;
			if (tmp[j]) cur += dif[j];
			if (cur>0) ok = false;
		}
		for (int j = n-1;j>i and ok;j--) {
			cur*=2;
			if (tmp[j]) cur+= dif[j];
			if (cur>0) ok = false;
		}
		if (cur==0 and ok) return true;
	}
	return false;
}

int main() {
//	freopen("input.txt","r",stdin);	
	std::ios::sync_with_stdio(false);cin.tie(0);
	cin>>n;
	rep(i,0,n) cin>>a[i]>>b[i],dif[i] = a[i]-b[i];
	dp[0] = hmm[0] = 1;
	rep(i,1,(1<<n)) {
		dp[i] = hmm[i] = check(i);
//		cout<<i<<" "<<check(i)<<endl;
	}
	rep(i,1,(1<<n))
		for (int j = (i-1)&i;j>0 and dp[i]==0;j = (j-1)&i) {
			if (dp[j]==1 and hmm[i^j]==1) {
				dp[i] = 1;
				break;
			}
		}
	if (dp[(1<<n)-1]) cout<<"Yes";
	else cout<<"No";
	return 0;
}

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