Submission #86010

#	Time	Username	Problem	Language	Result	Execution time	Memory
86010		liwi	Bali Sculptures (APIO15_sculpture)	C++11	37 / 100	13 ms	5088 KiB

sculpture

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
typedef tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;

#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
char _;
#define println printf("\n");
#define readln(x) getline(cin,x);
#define pb push_back
#define endl "\n"
#define MOD 1000000007
#define mp make_pair

#define MAXN 2005

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef unordered_map<int,int> umii;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,pii> triple;
typedef int8_t byte;

ll gcd(ll a, ll b) {return b == 0 ? a : gcd(b, a % b);}
ll fpow(ll  b, ll exp, ll mod){if(exp == 0) return 1;ll t = fpow(b,exp/2,mod);if(exp&1) return t*t%mod*b%mod;return t*t%mod;}
ll divmod(ll i, ll j, ll mod){i%=mod,j%=mod;return i*fpow(j,mod-2,mod)%mod;}

int num_elements,A,B,shift;
bool dp[MAXN][MAXN];
ll arr[MAXN],psa[MAXN],current,temp;

inline string getBinary(int num){
    string res = "";
    for(int i=4; i>=0 ;i--)
        if(num&(1<<i)) res+="1";
        else res+="0";
        return res;
}

inline bool valid(ll sum){
    ll first = ~(sum>>shift);
    //string a = getBinary(first), b = getBinary(temp>>shift);
    //cout<<a<<" "<<b<<endl;
    if((first&(temp>>shift)) == (temp>>shift)) return true;
    return false;
}

inline void solve(){
    memset(dp,false,sizeof dp);
    dp[0][0] = true;
    for(int i=1; i<=num_elements; i++){ //idx
        for(int k=1; k<=B; k++){ //groups
            for(int v=i-1; v>=0; v--){ //size of group
                ll sum = psa[i]-psa[v];
                if(valid(sum) && dp[v][k-1]){
                    dp[i][k] = true;
                    break;
                }
            }
        }
    }
}

int main(){
    scanf("%d %d %d",&num_elements,&A,&B);
    for(int i=1; i<=num_elements; i++){
        scanf(" %lld",&arr[i]);
        psa[i] = psa[i-1]+arr[i];
    }
    int lg = (int)log2(psa[num_elements]);
    for(int i=lg; i>=0; i--){
        shift = i;
        temp^=(1<<i);
        solve();
        bool works = false;
        for(int k=A; k<=B; k++){
            if(dp[num_elements][k]){
                works = true;
                break;
            }
        }
        if(!works){
            current^=(1<<i);
            temp^=(1<<i);
        }
    }
    printf("%lld\n",current);
}
/*
6 2 2
2 3 1 2 4 6
ans=11
*/

Compilation message (stderr)

sculpture.cpp: In function 'std::__cxx11::string getBinary(int)':
sculpture.cpp:39:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(int i=4; i>=0 ;i--)
     ^~~
sculpture.cpp:42:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
         return res;
         ^~~~~~
sculpture.cpp: In function 'int main()':
sculpture.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d",&num_elements,&A,&B);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:72:14: 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: 16 / 16
• Subtask 3: 21 / 21
• Subtask 4: 0 / 25
• Subtask 5: 0 / 29