Submission #252632

#	Time	Username	Problem	Language	Result	Execution time	Memory
252632		ChrisT	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	143 ms	508 KiB

sculpture

#include<bits/stdc++.h>
using namespace std;
const int MN = 2003;
int dpLow[MN], dpHigh[MN];
int main () { 
	int n, a, b;
	scanf("%d %d %d", &n, &a, &b);
	vector<int> v(n+1);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &v[i]);
	}
	long long bad = 0;
	for (int bit = 40; bit >= 0; bit--) {
		memset(dpLow,0x3f,sizeof dpLow); memset(dpHigh,-0x3f,sizeof dpHigh);
		dpLow[0] = dpHigh[0] = 0;
		for (int i = 1; i <= n; i++) {
			long long run = 0;
			for (int j = i; j >= 1; j--) {
				run += v[j];
				if (!(run & bad) && !(run >> bit & 1)) {
					dpLow[i] = min(dpLow[j-1] + 1, dpLow[i]);
					dpHigh[i] = max(dpHigh[j-1] + 1, dpHigh[i]);
				}
			}
		}
		if (dpLow[n] <= b && dpHigh[n] >= a) {
			bad |= 1LL << bit;
		}
	}
	printf ("%lld\n",((1LL << 41) - 1) ^ bad);
    return 0;
}

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:7:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &a, &b);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:10:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &v[i]);
   ~~~~~^~~~~~~~~~~~~

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