Submission #43777

#	Time	Username	Problem	Language	Result	Execution time	Memory
43777		Extazy	Bali Sculptures (APIO15_sculpture)	C++14	21 / 100	6 ms	2120 KiB

sculpture

#include <bits/stdc++.h>

using namespace std;

const int N = 2007;

int n,a,b;
long long ans;
bool used[N][N];
long long state[N][N];
long long arr[N];

long long get_sum(int l, int r) {
    return arr[r]-arr[l-1];
}

long long recurse(int pos, int groups) {
    if(groups<0) return 1000000000000000000;
    if(pos>n) {
        if(groups==0) return 0;
        return 1;
    }
    
    if(used[pos][groups]) return state[pos][groups];
    
    int i;
    long long ans=1000000000000000000;
    
    for(i=pos;i<=n;i++) {
        ans=min(ans,recurse(i+1,groups-1)|get_sum(pos,i));
    }
    
    used[pos][groups]=true;
    return state[pos][groups]=ans;
}

int main() {
    int i;
    
    scanf("%d %d %d", &n, &a, &b);
    for(i=1;i<=n;i++) {
        scanf("%lld", &arr[i]);
        arr[i]+=arr[i-1];
    }
    ans=recurse(1,a);
    while(++a<=b) ans=min(ans,recurse(1,a));
    printf("%lld\n", ans);
    
    return 0;
}

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:40:34: 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:42:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &arr[i]);
                               ^

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