Submission #506075

#	Time	Username	Problem	Language	Result	Execution time	Memory
506075		amukkalir	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	101 ms	16076 KiB

sculpture

#include <bits/stdc++.h> 
using namespace std; 

typedef long long ll; 
typedef unsigned long long ull; 

#define pii pair<ll,ll> 
#define se second 
#define fi first
#define pb push_back 
#define wek puts("wekwek")
#define wik puts("-------")

const int nax = 2e3; 
const ll INF = (1ll<<42)-1; 
int n, a, b; 
int dp[nax+5][nax+5]; 
int memo[nax+5]; 
ll p[nax+5];

ll sum (int l, int r) {
    return p[r] - p[l-1]; 
}

int f(int grup, int idx, ll x) {
    if(grup > b) return 0; 
    if(idx == n+1) {
        return (a <= grup && grup <= b); 
    }

    int &ret = dp[grup][idx]; 
    if(~ret) return ret; 

	ret = 0; 
    for(int j=idx; j<=n; j++) {
        if((x | sum(idx,j)) == x) {
			ret |= f(grup+1, j+1, x); 
		}
    }
	//cout << grup << " " << idx << " " << ret << endl; 
    return ret; 
}

int rec(int idx, ll x) { 
	if(idx == n+1) return 0; 
	int &ret = memo[idx]; 
	if(~ret) return ret; 
	ret = n+1; 
	for(int j=idx; j<=n; j++) {
		if((x | sum(idx,j)) == x) {
			ret = min(ret, 1 + rec(j+1, x)); 
		}
	}

	return ret; 
}

void solve() {
	ll lo = 0, hi = INF; 
    ll ans = hi; 
    while(lo <= hi) {
        ll mid = (lo+hi)/2; 
        memset(memo, -1, sizeof memo); 
		//cout << bitset<64> (mid) << endl; 
        if(rec(1, mid) <= b) {
            ans = mid; 
            hi = mid-1; 
        } else {
            lo = mid+1; 
        }
    }
	printf("%lld", ans); 
	exit(0); 
}

signed main () {	
    scanf("%d %d %d", &n, &a, &b);
    for(int i=1; i<=n; i++)  {
        scanf("%lld", &p[i]); 
        p[i] += p[i-1]; 
		//cout << i << " " << p[i] << endl; 
    }

	if(a==1) solve(); 

    ll lo = 0, hi = INF; 
    ll ans = hi; 
    while(lo <= hi) {
        ll mid = (lo+hi)/2; 
        memset(dp, -1, sizeof dp); 
		//cout << bitset<64> (mid) << endl; 
        if(f(0, 1, mid)) {
            ans = mid; 
            hi = mid-1; 
        } else {
            lo = mid+1; 
        }
    }

    printf("%lld", ans); 
}

/*

*/

Compilation message (stderr)

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

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