結果

問題 No.1463 Hungry Kanten
コンテスト
ユーザー tsuishi
提出日時 2021-04-13 16:18:52
言語 C
(gcc 13.3.0)
結果
MLE  
実行時間 -
コード長 3,699 bytes
コンパイル時間 363 ms
コンパイル使用メモリ 32,896 KB
実行使用メモリ 526,184 KB
最終ジャッジ日時 2024-06-29 21:22:17
合計ジャッジ時間 6,623 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample MLE * 2
other MLE * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
extern int getchar_unlocked(void);
extern int putchar_unlocked(int);
#define DEBUGg

#define NOP do{}while(0)
#define gc(d)	(d)=getchar_unlocked()
#define	pc(d) putchar_unlocked(d)
#define PRINCR pc('\n')
#ifdef DEBUG
#include <time.h>
#define TRACE(...) do{printf(__VA_ARGS__);fflush(stdout);}while(0)
#define TRACECR do{putchar_unlocked('\n');fflush(stdout);}while(0)
static clock_t	startclock;
void DEBUGSTART(void){TRACE("--DEBUG MODE --\n");startclock=clock();}
void DEBUGEND(void){startclock=clock()-startclock;TRACE("--finish --\ntime is %.3fms\n",startclock/1000.);}
#else
#define TRACE(...) NOP
#define TRACECR NOP
void DEBUGSTART(void){return;}
void DEBUGEND(void){return;}
#endif

#define NOCR(strig) do{char *p;p=strchr(strig,'\n');if(p)*p='\0';}while(0)
#define SWAP(type,a,b) do{type _c;_c=a;a=b;b=_c;}while(0)
#define MAX(a,b)	((a)>(b)?(a):(b))
#define MIN(a,b)	((a)<(b)?(a):(b))
#define REP(a,b) for(int a=0;a<(int)(b);++a)
#define REP1(a,b) for(int a=1;a<=(int)(b);++a)
static char *GETWORD(char* str) {char c;char *cp;cp=&str[0];gc(c);while(c!=EOF){if((c==' ')||(c=='\n'))break;*cp++=c;gc(c);}*cp='\0';return &str[0];}
#define GETLINE(str) do{char *p;fgets(str,sizeof(str),stdin);p=strchr(str,'\n');if(p)*p='\0';}while(0)
#define mygc(c) (c)=getchar()
static void read1(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
static void read2(int *x, int *y){read1(x);read1(y);}
#define INPUT(str) do{char *p;fgets(str,sizeof(str),stdin);p=strchr(str,'\n');if(p)*p='\0';}while(0)
#define REP(a,b) for(int a=0;a<(int)(b);++a)
#define lolong long long
static int GETLINEINT(void) {char s[34];GETLINE(s);return atoi(s);}
static int GETWORDINT(void) {char s[34];GETWORD(s);return atoi(s);}
static int cmpint123(const void *a,const void *b){if(*(int *)a>*(int *)b){return 1;}if(*(int *)a==*(int *)b){return 0;}return -1;}
static int cmpint321(const void *a,const void *b){if(*(int *)a<*(int *)b){return 1;}if(*(int *)a==*(int *)b){return 0;}return -1;}
#define	ull	unsigned long long
#define	ui	unsigned int
// *********************
#define	CAMA  (67108864LL)
int	seisuu[19];
int	K;
ull ncash[CAMA];
// *********************
ull inl()   // 整数の入力（負数に対応）
{
	ull n = 0ULL;
	int c;
	gc(c);
	do {
		n = 10 * n + (c & 0xf);
		gc(c);
	} while (c >= '0');
	return n;
}
void outl(ull n) {
	int i;
	char b[70];
	if (!n) pc('0');
	else {
		if (n < 0) pc('-'), n = -n;
		i = 0; while (n) b[i++] = n % 10 + '0', n /= 10;
		while (i--) pc(b[i]);
	}
	pc('\n');
}
ui bits_count( unsigned int v ) {
  v = (v & 0x55555555) + (v >>  1 & 0x55555555);
  v = (v & 0x33333333) + (v >>  2 & 0x33333333);
  v = (v & 0x0f0f0f0f) + (v >>  4 & 0x0f0f0f0f);
  v = (v & 0x00ff00ff) + (v >>  8 & 0x00ff00ff);
  v = (v & 0x0000ffff) + (v >> 16 & 0x0000ffff);
  return v;
}
void cook(ui x, ui *fry, ui *crush ) {
	ull f = 0L;
	ull c = 1L;
	int	*ip = &seisuu[0];
	while( x ) {
		if( x & 1 ) {
			f += *ip;
			c *= *ip;
		}
		x >>= 1;
		ip++;
	}
	*fry = f;
	*crush = c;
	return;
}
ui push( ui x ) {
	if( ncash[ x % CAMA] ) return 0;
	ncash[ x % CAMA ] = 1;
	//TRACE("p(%ud)",x);
	return 1;
}
// *********************
int main( void ) {
	int N;
	ui	bc = 0;
	ui f,c;
	ui	mbc;
	ui	ans = 0;

	memset( ncash , 0 , CAMA * sizeof(ull) );
	N = GETWORDINT();
	K = GETWORDINT();
	REP(i,N) {
		seisuu[i] = GETWORDINT();
	}
	mbc = (1 << N) +1;

	DEBUGSTART();
	for(ui i = 1; i < mbc; i++ ) {
		if( bits_count(i) >= K ) {
			cook(i, &f, &c );
			ans += push(f);
			ans += push(c);
		}
	}
	DEBUGEND();
	outl( ans );
}
0