oj.uz

Submission #520401

# Submission time Handle Problem Language Result Execution time Memory
520401 2022-01-29T19:03:30 Z amunduzbaev Football (info1cup20_football) C++14
100 / 100
 45 ms 2036 KB 
#include "bits/stdc++.h"
using namespace std;

#define ar array

const int N = 105;
int dp[N][N];

void solve(){
	int n, k; cin>>n>>k;
	vector<int> a(n);
	for(int i=0;i<n;i++) cin>>a[i];
	
	while(k){
		int sum = accumulate(a.begin(), a.end(), 0ll);
		if(sum & 1){
			cout<<1;
			return;
		}
		
		for(auto& x : a) x /= 2;
		k /= 2;
	}
	
	cout<<0;
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	dp[0][0] = 0;
	for(int i=1;i<N;i++){
		for(int j=1;j<=i;j++){
			vector<int> tt;
			for(int l=1;l<=j;l++){
				tt.push_back(dp[i-l][min(i-l, l)]);
			}
			sort(tt.begin(), tt.end());
			int last = 0;
			for(auto x : tt){
				if(x > last) break;
				if(x == last) last++;
			}
			
			dp[i][j] = last;
		}
	}
	
	int t; cin>>t;
	while(t--){
		solve();
	}
}

Subtask #1
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1348 KB Output is correct
2 Correct 14 ms 1300 KB Output is correct
3 Correct 15 ms 1292 KB Output is correct
4 Correct 15 ms 1380 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 332 KB Output is correct
2 Correct 4 ms 352 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Correct 4 ms 332 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 736 KB Output is correct
2 Correct 11 ms 600 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 1020 KB Output is correct
2 Correct 29 ms 964 KB Output is correct
3 Correct 27 ms 1060 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 2036 KB Output is correct
2 Correct 39 ms 2016 KB Output is correct
3 Correct 45 ms 2024 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1320 KB Output is correct
2 Correct 14 ms 1392 KB Output is correct
3 Correct 18 ms 1316 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1312 KB Output is correct
2 Correct 14 ms 1360 KB Output is correct
3 Correct 17 ms 1316 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1304 KB Output is correct
2 Correct 16 ms 1352 KB Output is correct