Submission #856932


Source Code Expand

Copy
#include <iostream>
#include <stdio.h>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <cmath>
#include <string>

using namespace std;

typedef vector <int> VI;
typedef vector <VI> VVI;
typedef vector <string> VS;
typedef pair<int,int> PII;
typedef long long LL;
typedef vector <LL> VLL;
typedef unsigned long long ULL;
typedef pair <int, LL> PIL;
typedef vector <PIL> VPIL;


//#define each(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
//#define sort(c) sort((c).begin(),(c).end())

#define range(i,a,b) for(int i=(a); i < (b); i++)
#define rep(i,n) range(i,0,n)

int bit_cnt(LL b){
	int cnt = 0;
	while (b != 0){
		cnt += (b % 2);
		b /= 2;
	}
	return cnt;
}

int x[50];
int L[1<<25];
map <int,LL> enume(int n, int ofs,int A){
	map <int,LL> D;
	LL jbit,nbit;
	int nv;
	D[0] += 1;
	for(LL i = 0; i<(1<<n); i++) L[i] = -1;
	L[0] = 0;
	for(LL k = 0; k < (1<<n); k++){
		rep(j,n){
			jbit = 1<<j;
			if ((k&jbit) != 0) continue;
			nbit = k + jbit;
			if (L[nbit] != -1) continue;
			nv = L[k] + x[j+ofs];
			L[nbit] = nv;
			D[nv-A*bit_cnt(nbit)] += 1;
		}
	}
	return D;
}

int main(){
	int N,A,n1,n2;
	LL ans = 0;
	map <int,LL> D1,D2;
	map <int,LL> :: iterator it;
	scanf("%d %d",&N,&A);
	rep(i,N) scanf("%d",x+i);
	n1 = N/2;
	n2 = N - n1;
	D1 = enume(n1,0,A);
	D2 = enume(n2,n1,A);
	for (it = D1.begin();it!=D1.end();it++){
		ans += it->second*D2[-(it->first)];
	}
	printf("%lld",ans-1);
	return 0;
}

Submission Info

Submission Time
Task C - Tak and Cards
User taktah
Language C++14 (GCC 5.4.1)
Score 200
Code Size 1579 Byte
Status TLE
Exec Time 2117 ms
Memory 131328 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:69:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&N,&A);
                      ^
./Main.cpp:70:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  rep(i,N) scanf("%d",x+i);
                          ^

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 200 / 200 0 / 100
Status
AC × 4
AC × 12
AC × 17
TLE × 7
Set Name Test Cases
Sample example_01.txt, example_02.txt, example_03.txt, example_04.txt
Subtask1 example_01.txt, example_02.txt, example_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt
All example_01.txt, example_02.txt, example_03.txt, example_04.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt
Case Name Status Exec Time Memory
example_01.txt AC 4 ms 256 KB
example_02.txt AC 4 ms 256 KB
example_03.txt AC 4 ms 256 KB
example_04.txt AC 36 ms 896 KB
subtask1_01.txt AC 4 ms 256 KB
subtask1_02.txt AC 4 ms 256 KB
subtask1_03.txt AC 4 ms 256 KB
subtask1_04.txt AC 4 ms 256 KB
subtask1_05.txt AC 4 ms 256 KB
subtask1_06.txt AC 4 ms 256 KB
subtask1_07.txt AC 4 ms 256 KB
subtask1_08.txt AC 4 ms 256 KB
subtask1_09.txt AC 4 ms 256 KB
subtask2_01.txt TLE 2117 ms 131328 KB
subtask2_02.txt TLE 2113 ms 131328 KB
subtask2_03.txt TLE 2111 ms 65792 KB
subtask2_04.txt TLE 2114 ms 131328 KB
subtask2_05.txt TLE 2117 ms 131328 KB
subtask2_06.txt TLE 2117 ms 131328 KB
subtask2_07.txt TLE 2117 ms 131328 KB
subtask2_08.txt AC 45 ms 768 KB
subtask2_09.txt AC 43 ms 768 KB
subtask2_10.txt AC 698 ms 8448 KB
subtask2_11.txt AC 1421 ms 16640 KB