답안 #86010

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
86010	2018-11-24T03:57:46 Z	liwi	Bali Sculptures (APIO15_sculpture)	C++11	37 / 100	13 ms	5088 KB

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

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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-