Submission #1223294

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223294		mingga	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	86 ms	660 KiB

sculpture

#include "bits/stdc++.h"

using namespace std;

#define ln "\n"
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define ll long long
const int mod = 1e9 + 7;
const int inf = 2e9;
const int N = 2005;
int n, A, B, a[N], dp[N][N];
ll ps[N];
int ans[N];


namespace sub4 {
	bool check() {
		return n <= 100;
	}
	bool dp[N][N];
	void solve() {
		ll ans = 0;
		for(int t = 37; t >= 0; t--) {
			dp[0][0] = 1;
			for(int i = 1; i <= n; i++) 
				for(int j = 1; j <= n; j++)  dp[i][j] = 0;
			for(int i = 1; i <= n; i++) {
				for(int j = 1; j <= i; j++) {
					for(int k = i - 1; k >= 0; k--) {
						ll summ = ps[i] - ps[k];
						if(((summ >> t) & (ans >> t)) == (summ >> t)) {
							dp[i][j] = dp[i][j] || dp[k][j - 1];
						}
					}
				}
			}
			bool ok = 0;
			for(int i = A; i <= B; i++) {
				if(dp[n][i]) {
					ok = 1;
					break;
				}
			}
			if(!ok) ans += (1ll << t);
		}
		cout << ans << ln;
	}
}

namespace sub5 {
	int dp[N];
	bool check() {
		return A == 1;
	}
	void solve() {
		ll ans = 0;
		for(int t = 41; t >= 0; t--) {
			memset(dp, 0x3f, sizeof dp);
			dp[0] = 0;
			for(int i = 1; i <= n; i++) {
				for(int j = 0; j < i; j++) {
					ll summ = ps[i] - ps[j];
					if(((summ >> t) & (ans >> t)) == (summ >> t)) {
						dp[i] = min(dp[i], dp[j] + 1);
					}
				}
			}
			if(dp[n] > B) ans += (1ll << t);
		}
		cout << ans << ln;
	}
}

signed main() {
	cin.tie(0) -> sync_with_stdio(0);
	#define task ""
	if(fopen(task ".INP", "r")) {
		freopen(task ".INP", "r", stdin);
		freopen(task ".OUT", "w", stdout);
	}
	cin >> n >> A >> B;
	for(int i = 1; i <= n; i++) cin >> a[i], ps[i] = ps[i - 1] + 1ll * a[i];
	if(sub4::check()) sub4::solve();
	else if(sub5::check()) sub5::solve();
    cerr << "\nTime: " << clock() * 1000 / CLOCKS_PER_SEC;
}

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:82:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |                 freopen(task ".INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:83:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |                 freopen(task ".OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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