Submission #1515102


Source Code Expand

#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define pb push_back
int dy[]={0, 0, 1, -1, 1, 1, -1, -1};
int dx[]={1, -1, 0, 0, 1, -1, -1, 1};

#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define mp make_pair
int n,x;
int w[32];
struct P{
    int fi,sc;

    bool operator<(const P& a) const{
        return fi < a.fi;
    }
};

bool al[40];
vector<P> sum[9];
void getsum(int s,int i,int d,int b){
    if(b == d){
        int a = 0;
        REP(j,n){
            a *= 2;
            a += al[j];
        }
        sum[b].pb((P){s,a});
        return;
    }
    FOR(j,i,n){
        al[j] = true;
        getsum(s + w[j],j + 1,d + 1,b);
        al[j] = false;
    }
}
int c = 0;

unordered_set<int> used;

void cou(int k,int x,bool f){
    int a = k / 2;
    int b = (k + 1) / 2;
    for (auto& e : sum[a]) {
        vector<P>::iterator it = lower_bound(sum[b].begin(),sum[b].end(),(P){x - e.fi,0});
        while(it != sum[b].end() && x - e.fi == it->fi){
            int bit1 = (e.sc | it->sc);
            if(f){
                int bit2 = 0; 
                REP(i,32){
                    bit2 *= 2;
                    bit2 += 1;
                }
                bit1 = (bit1 ^ bit2);
            }
            if((e.sc & it->sc) == 0 && used.find(bit1) == used.end()){
                c++;
                used.insert(bit1);
            }
            it++;
        }
    }
}

int main(){
    scanf("%d%d",&n,&x);
    REP(i,n)
        scanf("%d",w + i);

    int m = (n + 1) / 2;
    int l = (m + 1) / 2;

    FOR(i,1,l + 1){
        fill(al,al + n,false);
        getsum(0,0,0,i);
    }
    FOR(i,1,l + 1)
        sort(sum[i].begin(),sum[i].end());

    FOR(i,1,m + 1){
        cou(i,x,false);
    }
    int s = 0;
    REP(i,n)
        s += w[i];
    if(s == x)
        c++;
    FOR(i,m + 1,n){
        cou(n - i,s - x,true);
    }

    printf("%d\n",c);

    return 0;
}

Submission Info

Submission Time
Task C - 無駄なものが嫌いな人
User kyawakyawa
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2166 Byte
Status TLE
Exec Time 2108 ms
Memory 238416 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:71:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&x);
                        ^
./Main.cpp:73:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",w + i);
                          ^

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
AC × 11
TLE × 17
Set Name Test Cases
All max_1.txt, max_2.txt, max_3.txt, max_4.txt, pair_1.txt, pair_2.txt, power2_1.txt, power2_2.txt, power2_3.txt, power2_4.txt, power2_5.txt, random_1.txt, random_2.txt, random_3.txt, random_4.txt, random_5.txt, random_6.txt, random_7.txt, random_8.txt, random_9.txt, sample_1.txt, sample_2.txt, sample_3.txt, sample_4.txt, small_1.txt, small_2.txt, small_3.txt, small_4.txt
Case Name Status Exec Time Memory
max_1.txt TLE 2108 ms 238416 KB
max_2.txt TLE 2107 ms 192984 KB
max_3.txt TLE 2106 ms 167644 KB
max_4.txt TLE 2105 ms 169436 KB
pair_1.txt TLE 2104 ms 170204 KB
pair_2.txt TLE 2108 ms 199384 KB
power2_1.txt TLE 2104 ms 167644 KB
power2_2.txt TLE 2104 ms 167900 KB
power2_3.txt TLE 2105 ms 170460 KB
power2_4.txt TLE 2105 ms 170076 KB
power2_5.txt AC 87 ms 10096 KB
random_1.txt AC 1835 ms 94560 KB
random_2.txt TLE 2104 ms 94944 KB
random_3.txt TLE 2104 ms 168412 KB
random_4.txt TLE 2104 ms 170972 KB
random_5.txt TLE 2105 ms 170076 KB
random_6.txt TLE 2104 ms 97024 KB
random_7.txt TLE 2108 ms 191704 KB
random_8.txt TLE 2104 ms 168284 KB
random_9.txt AC 1710 ms 97760 KB
sample_1.txt AC 1 ms 256 KB
sample_2.txt AC 1 ms 256 KB
sample_3.txt AC 3 ms 512 KB
sample_4.txt AC 34 ms 768 KB
small_1.txt AC 1 ms 256 KB
small_2.txt AC 1 ms 256 KB
small_3.txt AC 1 ms 256 KB
small_4.txt AC 1 ms 256 KB