Submission #558731

#	Time	Username	Problem	Language	Result	Execution time	Memory
558731		hhhhaura	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	188 ms	380 KiB

sculpture

#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse")
#pragma loop-opt(on)
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rrep(i, a, b) for(int i = b; i >= a; i --)
#define all(x) x.begin(), x.end()
#define ceil(a, b) ((a + b - 1) / (b))
#define int long long int
#define lld long double
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())
#define INF 1000000000000000000
#define MOD 1000000007
#define eps (1e-9)
using namespace std;
#ifdef wiwihorz
#define print(a...)cerr<<"Line "<<__LINE__<<":",kout("["+string(#a)+"] = ", a)
void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
void kout() { cerr << endl; }
template<class T1,class ... T2>void kout(T1 a,T2 ... e){cerr<<a<<" ",kout(e...);}
#else
#define print(...) 0
#define vprint(...) 0
#endif
namespace solver1 {
	int n, A, B;
	const int P = 40;
	vector<int> v;
	vector<vector<int>> dp;
	void init_(int _n, int _A, int _B) {
		n = _n, A = _A, B = _B;
		v.assign(n + 1, 0);
		dp.assign(n + 1, vector<int>(n + 1, 0));
	}
	int check(int id, int mask) {
		dp.assign(n + 1, vector<int>(n + 1, 0));
		dp[0][0] = 1;
		int tot = (1ll << P) - 1;
		rep(i, 1, B) rep(j, 1, n) {
			rep(k, 0, j - 1) if(dp[i - 1][k]){
				int val = v[j] - v[k];
				if(((val ^ tot) & mask) == mask) dp[i][j] = 1;
			}
		}
		int ans = 0;
		rep(i, A, B) ans |= dp[i][n];
		return ans;
	}
	void solve() {
		int ans = 0;
		rep(i, 1, n) v[i] += v[i - 1];
		rrep(i, 0, P - 1) ans |= check(i, ans | (1ll << i)) << i;
		int tot = (1ll << P) - 1;
		cout << (tot ^ ans) << "\n";
	}
};
namespace solver2 {
	int n, A, B;
	const int P = 50;
	vector<int> v, dp;
	void init_(int _n, int _A, int _B) {
		n = _n, A = _A, B = _B;
		v.assign(n + 1, 0);
		dp.assign(n + 1, 0);
	}
	int check(int id, int mask) {
		int tot = (1ll << P) - 1;
		dp.assign(n + 1, INF);
		dp[0] = 0;
		rep(i, 1, n) rep(j, 0, i - 1) {
			int val = v[i] - v[j];
			if(((val ^ tot) & mask) == mask) 
				dp[i] = min(dp[i], dp[j] + 1);
		}
		return dp[n] <= B;
	}
	void solve() {
		assert(A == 1);
		int ans = 0, tot = (1ll << P) - 1;
		rep(i, 1, n) v[i] += v[i - 1];
		rrep(i, 0, P - 1) ans |= check(i, ans | (1ll << i)) << i;
		cout << (tot ^ ans) << "\n";
	}
};
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int n, A, B;
	cin >> n >> A >> B;
	if(A == 1) {
		solver2::init_(n, A, B);
		rep(i, 1, n) cin >> solver2::v[i];
		solver2::solve();
	}
	else {
		solver1::init_(n, A, B);
		rep(i, 1, n) cin >> solver1::v[i];
		solver1::solve();
	}
	return 0;
}

Compilation message (stderr)

sculpture.cpp:5: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    5 | #pragma loop-opt(on)
      | 
sculpture.cpp:20:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
      |             ^~~~
sculpture.cpp:20:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
      |                    ^~~~

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