oj.uz

Submission #86010

# Submission time Handle Problem Language Result Execution time Memory
86010 2018-11-24T03:57:46 Z liwi Bali Sculptures (APIO15_sculpture) C++11
37 / 100
 13 ms 5088 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4216 KB Output is correct
2 Correct 6 ms 4352 KB Output is correct
3 Correct 2 ms 4352 KB Output is correct
4 Correct 6 ms 4408 KB Output is correct
5 Correct 7 ms 4408 KB Output is correct
6 Correct 7 ms 4588 KB Output is correct
7 Correct 6 ms 4588 KB Output is correct
8 Correct 7 ms 4588 KB Output is correct
9 Correct 6 ms 4588 KB Output is correct
10 Correct 7 ms 4588 KB Output is correct
11 Correct 6 ms 4588 KB Output is correct
12 Correct 7 ms 4588 KB Output is correct
13 Correct 7 ms 4588 KB Output is correct
14 Correct 6 ms 4588 KB Output is correct
15 Correct 6 ms 4588 KB Output is correct
16 Correct 7 ms 4588 KB Output is correct
17 Correct 6 ms 4588 KB Output is correct
18 Correct 6 ms 4588 KB Output is correct
19 Correct 6 ms 4588 KB Output is correct
20 Correct 6 ms 4588 KB Output is correct
21 Correct 6 ms 4588 KB Output is correct
22 Correct 7 ms 4588 KB Output is correct
23 Correct 7 ms 4588 KB Output is correct
24 Correct 7 ms 4588 KB Output is correct
25 Correct 6 ms 4588 KB Output is correct
26 Correct 6 ms 4588 KB Output is correct
27 Correct 12 ms 4712 KB Output is correct
28 Incorrect 12 ms 4712 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4712 KB Output is correct
2 Correct 6 ms 4712 KB Output is correct
3 Correct 2 ms 4712 KB Output is correct
4 Correct 6 ms 4712 KB Output is correct
5 Correct 6 ms 4712 KB Output is correct
6 Correct 7 ms 4712 KB Output is correct
7 Correct 6 ms 4712 KB Output is correct
8 Correct 7 ms 4712 KB Output is correct
9 Correct 7 ms 4712 KB Output is correct
10 Correct 7 ms 4712 KB Output is correct
11 Correct 7 ms 4712 KB Output is correct
12 Correct 7 ms 4712 KB Output is correct
13 Correct 7 ms 4712 KB Output is correct
14 Correct 5 ms 4712 KB Output is correct
15 Correct 6 ms 4712 KB Output is correct
16 Correct 6 ms 4712 KB Output is correct
17 Correct 6 ms 4712 KB Output is correct
18 Correct 7 ms 4712 KB Output is correct
19 Correct 6 ms 4712 KB Output is correct
20 Correct 6 ms 4788 KB Output is correct
21 Correct 6 ms 4788 KB Output is correct
22 Correct 6 ms 4788 KB Output is correct
23 Correct 6 ms 4788 KB Output is correct
24 Correct 7 ms 4788 KB Output is correct
25 Correct 6 ms 4788 KB Output is correct
26 Correct 6 ms 4788 KB Output is correct
27 Correct 6 ms 4788 KB Output is correct
28 Correct 7 ms 4788 KB Output is correct
29 Correct 6 ms 4788 KB Output is correct
30 Correct 6 ms 4788 KB Output is correct
31 Correct 7 ms 4788 KB Output is correct
32 Correct 7 ms 4788 KB Output is correct
33 Correct 7 ms 4788 KB Output is correct
34 Correct 7 ms 4788 KB Output is correct
35 Correct 7 ms 4788 KB Output is correct
36 Correct 7 ms 4788 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4788 KB Output is correct
2 Correct 6 ms 4788 KB Output is correct
3 Correct 2 ms 4788 KB Output is correct
4 Correct 6 ms 4788 KB Output is correct
5 Correct 6 ms 4788 KB Output is correct
6 Correct 6 ms 4788 KB Output is correct
7 Correct 6 ms 4788 KB Output is correct
8 Correct 7 ms 4788 KB Output is correct
9 Correct 6 ms 4788 KB Output is correct
10 Correct 7 ms 4788 KB Output is correct
11 Correct 7 ms 4788 KB Output is correct
12 Correct 6 ms 4788 KB Output is correct
13 Correct 6 ms 4788 KB Output is correct
14 Correct 6 ms 4788 KB Output is correct
15 Correct 7 ms 4820 KB Output is correct
16 Correct 6 ms 4820 KB Output is correct
17 Correct 6 ms 4820 KB Output is correct
18 Correct 7 ms 4924 KB Output is correct
19 Correct 7 ms 4924 KB Output is correct
20 Correct 7 ms 4924 KB Output is correct
21 Correct 7 ms 4924 KB Output is correct
22 Correct 7 ms 4924 KB Output is correct
23 Correct 7 ms 4924 KB Output is correct
24 Correct 7 ms 4924 KB Output is correct
25 Correct 7 ms 4924 KB Output is correct
26 Correct 8 ms 4924 KB Output is correct
27 Correct 9 ms 4924 KB Output is correct
28 Correct 12 ms 4924 KB Output is correct
29 Correct 13 ms 4924 KB Output is correct
30 Correct 7 ms 4924 KB Output is correct
31 Correct 9 ms 4924 KB Output is correct
32 Correct 11 ms 4924 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4924 KB Output is correct
2 Correct 6 ms 4924 KB Output is correct
3 Correct 2 ms 4924 KB Output is correct
4 Correct 6 ms 4924 KB Output is correct
5 Correct 6 ms 4924 KB Output is correct
6 Correct 7 ms 4924 KB Output is correct
7 Correct 6 ms 4924 KB Output is correct
8 Correct 7 ms 4924 KB Output is correct
9 Correct 6 ms 4924 KB Output is correct
10 Correct 6 ms 4924 KB Output is correct
11 Correct 7 ms 4924 KB Output is correct
12 Correct 7 ms 4928 KB Output is correct
13 Correct 6 ms 4928 KB Output is correct
14 Correct 5 ms 4928 KB Output is correct
15 Correct 6 ms 4928 KB Output is correct
16 Correct 6 ms 4928 KB Output is correct
17 Correct 6 ms 4928 KB Output is correct
18 Correct 7 ms 4928 KB Output is correct
19 Correct 6 ms 4928 KB Output is correct
20 Correct 7 ms 4928 KB Output is correct
21 Correct 7 ms 4928 KB Output is correct
22 Correct 7 ms 4932 KB Output is correct
23 Correct 7 ms 4936 KB Output is correct
24 Correct 7 ms 5008 KB Output is correct
25 Correct 6 ms 5008 KB Output is correct
26 Correct 7 ms 5008 KB Output is correct
27 Correct 12 ms 5008 KB Output is correct
28 Incorrect 11 ms 5008 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5008 KB Output is correct
2 Correct 6 ms 5008 KB Output is correct
3 Correct 2 ms 5008 KB Output is correct
4 Correct 6 ms 5008 KB Output is correct
5 Correct 6 ms 5008 KB Output is correct
6 Correct 7 ms 5008 KB Output is correct
7 Correct 7 ms 5008 KB Output is correct
8 Correct 6 ms 5008 KB Output is correct
9 Correct 7 ms 5008 KB Output is correct
10 Correct 8 ms 5008 KB Output is correct
11 Correct 8 ms 5008 KB Output is correct
12 Correct 6 ms 5008 KB Output is correct
13 Correct 6 ms 5008 KB Output is correct
14 Correct 11 ms 5088 KB Output is correct
15 Incorrect 11 ms 5088 KB Output isn't correct
16 Halted 0 ms 0 KB -