oj.uz

Submission #741524

# Submission time Handle Problem Language Result Execution time Memory
741524 2023-05-14T09:47:10 Z myrcella Remittance (JOI19_remittance) C++17
0 / 100
 1 ms 340 KB 
//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) {
	vector <int> tmp;
	rep(i,0,n) if ((mask>>i)&1) {
		tmp.pb(i);
	}
	rep(i,0,SZ(tmp)) {
		int lst = 0;
		bool ok = true;
		rep(j,i,SZ(tmp)) {
			if (j!=i) {
				rep(k,0,tmp[j] - tmp[j-1]) {
					if (lst%2==1) {
						ok = false;
						break;
					}
					else  lst/=2;
				}
			}
			int cur = dif[tmp[j]] + lst;
			if (cur<0) ok = false;
			lst  = cur;
			if (ok==false) break;
		}
		rep(k,0,n-tmp.back()) {
			if (lst%2==1) ok =false;
			lst/=2;
		}
		rep(k,0,tmp[0]) {
			if (lst%2==1) ok =false;
			lst/=2;
		}
		rep(j,0,i) {
			if (j!=0) {
				rep(k,0,tmp[j] - tmp[j-1]) {
					if (lst%2==1) {
						ok = false;
						break;
					}
					else  lst/=2;
				}
			}
			int cur = dif[tmp[j]] + lst;
			if (cur<0) ok = false;
			if (ok==false) break;
			lst = cur;
		}
		if (ok and lst==0) 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);
//		if (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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Incorrect 1 ms 328 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Incorrect 1 ms 328 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Incorrect 1 ms 328 KB Output isn't correct
9 Halted 0 ms 0 KB -