Submission #123545

#	Time	Username	Problem	Language	Result	Execution time	Memory
123545		egorlifar	Bali Sculptures (APIO15_sculpture)	C++17	50 / 100	126 ms	504 KiB

sculpture

/*
ЗАПУСКАЕМ 
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░ 
 */
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
    
     
using namespace std;
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; } 
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left228
#define right right228
#define next next228
#define rank rank228
#define prev prev228
#define y1 y1228                                                         
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define files(FILENAME) read(FILENAME), write(FILENAME)
#define pb push_back
const string FILENAME = "input";
const int MAXN = 2000;


int n, a, b;
int y[MAXN];
bool dp[101][101];
int dp1[2001];


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//read(FILENAME);
	cin >> n >> a >> b;
	for (int i = 0; i < n; i++) {
		cin >> y[i];
	}
	long long res = 0;
	for (int it = 42; it >= 0; it--) {
		if (a == 1) {
			for (int i = 1; i <= n; i++) {
				dp1[i] = 1e9;
			}
			for (int i = 0; i < n; i++) {
				long long sum = 0;
				for (int j = i; j < n; j++) {
					sum += y[j];
					if (((sum & res) ^ sum) >> it) {
						continue;
					}
					chkmin(dp1[j + 1], dp1[i] + 1);
				}	
			}
			if (dp1[n] > b) {
				res |= 1LL << it;
			}
		} else {
			memset(dp, 0, sizeof(dp));
			for (int i = 0; i < n; i++) {
				for (int k = 0; k <= i; k++) {
					long long sum = 0;
					for (int j = i; j < n; j++) {
						sum += y[j];
						if (((sum & res) ^ sum) >> it) {
							continue;
						}
						dp[j + 1][k + 1] |= dp[i][k];
					}	
				}
			}
			bool ok = false;
			for (int k = a; k <= b; k++) {
				if (dp[n][k]) {
					ok = true;
					break;
				}
			}
			if (!ok) {
				res += 1LL << it;
			}
		}
	}		
	cout << res << endl;
	return 0;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 16
• Subtask 3: 21 / 21
• Subtask 4: 0 / 25
• Subtask 5: 29 / 29