Submission #41402

#	Time	Username	Problem	Language	Result	Execution time	Memory
41402		fest	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	462 ms	211544 KiB

sculpture

// fest
#include <bits/stdc++.h>	

#define pb push_back
#define F first
#define S second
#define y1 dasdasfasfas
#define x1 wqdadfasfasfas
#define All(c) c.begin(), c.end()
#define SZ(A) (int((A).size()))
#define umap unordered_map
#define FILENAME ""
#define __ fflush(stdout)

typedef long long ll;
typedef long double ld;    

using namespace std;

void FREOPEN() {
	#ifdef COMP
		freopen(".in", "r", stdin);
		freopen("2.out", "w", stdout);
	#else
		freopen(FILENAME".in", "r", stdin);
		freopen(FILENAME".out", "w", stdout);
	#endif
}                           

inline double Time() {return (clock() * 1.0) / CLOCKS_PER_SEC; }             

const int N = 2001, inf = 1e9 * 2, MOD = (int)1e9 + 7, M = 42;

char CH[N];

const ll INF = 1e18;

const int dx[] = {1, -1, 0, 0, -1, 1, -1, 1};
const int dy[] = {0, 0, 1, -1, -1, 1, 1, -1};

ll a[N];               

int d[N];

map<ll, bool> dp[N][N];

void solve1(int n, int r) {
  for (int i = 1; i <= n; i++) scanf("%lld ", a + i);
	ll ans = 0;
	ll no = 0;
	for (int bit = M - 1; bit >= 0; bit--) {
		ll now = (ans | (1ll << bit));
		now--;
		no |= (1ll << bit);
		for (int i = 1; i <= n; i++) d[i] = inf;
		for (int i = 1; i <= n; i++) {
			ll sum = a[i];
			for (int j = i - 1; j >= 0; j--) {
				if (sum & no) {
					sum += a[j];
					continue;
				}
				if (sum > now) break;
				d[i] = min(d[i], d[j] + 1);	
				sum += a[j];
			}
		}
		no ^= (1ll << bit);
		if (d[n] <= r) no |= (1ll << bit);
		else ans |= (1ll << bit);
	}
	cout << ans;
}

void solve2(int n, int l, int r) {
	for (int i = 1; i <= n; i++) scanf("%lld ", a + i);
	ll should = INF;
	for (int i = 50; i >= 0; i--) {
		int bl = 0;
		for (int j = 1; j <= n;) {
			ll now = a[j];
			int rig = j + 1;
			while (rig <= n && now + a[rig] < (1ll << i)) now += a[rig], rig++;
			if (now >= (1ll << i)) {
				bl = r + 1;
				break;
			}
			bl++;
			j = rig;	
		}
		if (bl <= r) should = (1ll << i);
		else break;
	}
	dp[0][0][0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int k = 1; k <= r; k++) {
			ll sum = a[i];
			for (int j = i - 1; j >= 0; j--) {
				if (sum >= should) break;
				for (auto m : dp[j][k - 1]) if ((m.F | sum) < should) dp[i][k][(m.F | sum)] = 1;
				sum += a[j];	
			}
		}
	}
	ll ans = INF;
	for (int k = l; k <= r; k++) for (auto m : dp[n][k]) ans = min(ans, m.F);
	cout << ans;	
}

int main() {
  
	int n, l, r;
	cin >> n >> l >> r;
	if (l == 1) solve1(n, r);
	else solve2(n, l, r);
	return 0;	
}

Compilation message (stderr)

sculpture.cpp: In function 'void FREOPEN()':
sculpture.cpp:25:37: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(FILENAME".in", "r", stdin);
                                     ^
sculpture.cpp:26:39: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(FILENAME".out", "w", stdout);
                                       ^
sculpture.cpp: In function 'void solve1(int, int)':
sculpture.cpp:48:53: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for (int i = 1; i <= n; i++) scanf("%lld ", a + i);
                                                     ^
sculpture.cpp: In function 'void solve2(int, int, int)':
sculpture.cpp:76:52: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= n; i++) scanf("%lld ", a + i);
                                                    ^

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