Submission #497864

#	Time	Username	Problem	Language	Result	Execution time	Memory
497864		amukkalir	Bali Sculptures (APIO15_sculpture)	C++17	21 / 100	21 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) return INF; 

    ll &res = dp[rem][idx]; 
    if(~res) return res; 
    if(rem == 1) return res = p[n] - p[idx-1]; 

    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, 1)); 
        //cout << i << " " << f(i, 1) << 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 'int main()':
sculpture.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     scanf("%d%d%d", &n, &a, &b);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:38:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         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