Submission #505053

#	Time	Username	Problem	Language	Result	Execution time	Memory
505053		amukkalir	Bali Sculptures (APIO15_sculpture)	C++17	21 / 100	16 ms	31820 KiB

sculpture

#include <bits/stdc++.h> 
using namespace std; 
typedef long long ll; 
 
#define pii pair<int,int> 
#define fi first 
#define se second
 
const ll INF = LLONG_MAX; 
const int nax = 2000; 
 
ll dp[nax+5][nax+5]; 
ll p[nax+5]; 
int n; 
 
ll f (int rem, int idx) {
    if(idx==n+1) return (rem==0)?0:INF; 
    if(rem<=0 && idx != n+1) return INF; 
 
    ll &res = dp[rem][idx]; 
    if(~res) return res; 
 
    res = INF; 
    for(int i=idx; i<=n; i++) {
        res = min(res, p[i]-p[idx-1] | f(rem-1, i+1)); 
    }
 
    return res; 
}
 
signed main () {
    int a, b; 
 
    scanf("%d%d%d", &n, &a, &b); 
    for(int i=1; i<=n; i++) {
        ll y; scanf("%lld", &y); 
        p[i] = p[i-1] + y; 
    }
 
    ll ans = INF; 
    memset(dp, -1, sizeof dp); 
    for(int i=a; i<=b; i++) {
        ans = min(ans, f(i, 0)); 
        //cout << i << " " << f(i, 0) << endl; 
    }
 
    printf("%lld", ans); 
}
 
/*
YES
3 1 3 
YES
1 
NO
YES
5 5 4 1 4 5 
*/

Compilation message (stderr)

sculpture.cpp: In function 'll f(int, int)':
sculpture.cpp:25:28: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
   25 |         res = min(res, p[i]-p[idx-1] | f(rem-1, i+1));
      |                        ~~~~^~~~~~~~~
sculpture.cpp: In function 'int main()':
sculpture.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     scanf("%d%d%d", &n, &a, &b);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:36:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         ll y; scanf("%lld", &y);
      |               ~~~~~^~~~~~~~~~~~

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