結果

問題 No.626 Randomized 01 Knapsack
ユーザー tailstails
提出日時 2017-12-18 19:43:41
言語 C
(gcc 12.3.0)
結果
WA  
実行時間 -
コード長 860 bytes
コンパイル時間 198 ms
コンパイル使用メモリ 30,336 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-12-16 00:28:14
合計ジャッジ時間 36,398 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,820 KB
testcase_01 AC 1 ms
6,816 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 1 ms
6,816 KB
testcase_04 AC 290 ms
6,816 KB
testcase_05 AC 1 ms
6,820 KB
testcase_06 AC 1,950 ms
6,820 KB
testcase_07 AC 1,951 ms
6,816 KB
testcase_08 AC 1,950 ms
6,820 KB
testcase_09 AC 1,951 ms
6,816 KB
testcase_10 AC 1,951 ms
6,820 KB
testcase_11 AC 1,951 ms
6,816 KB
testcase_12 WA -
testcase_13 AC 1,951 ms
6,820 KB
testcase_14 AC 1,951 ms
6,820 KB
testcase_15 WA -
testcase_16 AC 1,951 ms
6,816 KB
testcase_17 WA -
testcase_18 AC 1,951 ms
6,820 KB
testcase_19 WA -
testcase_20 AC 1,951 ms
6,820 KB
testcase_21 WA -
testcase_22 AC 1,952 ms
6,816 KB
testcase_23 WA -
testcase_24 AC 3 ms
6,816 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function 'ha':
main.c:12:9: warning: implicit declaration of function 'printf' [-Wimplicit-function-declaration]
   12 |         printf("%lld\n",b);
      |         ^~~~~~
main.c:2:1: note: include '<stdio.h>' or provide a declaration of 'printf'
    1 | #include <sys/time.h>
  +++ |+#include <stdio.h>
    2 | 
main.c:12:9: warning: incompatible implicit declaration of built-in function 'printf' [-Wbuiltin-declaration-mismatch]
   12 |         printf("%lld\n",b);
      |         ^~~~~~
main.c:12:9: note: include '<stdio.h>' or provide a declaration of 'printf'
main.c:13:9: warning: implicit declaration of function 'exit' [-Wimplicit-function-declaration]
   13 |         exit(0);
      |         ^~~~
main.c:2:1: note: include '<stdlib.h>' or provide a declaration of 'exit'
    1 | #include <sys/time.h>
  +++ |+#include <stdlib.h>
    2 | 
main.c:13:9: warning: incompatible implicit declaration of built-in function 'exit' [-Wbuiltin-declaration-mismatch]
   13 |         exit(0);
      |         ^~~~
main.c:13:9: note: include '<stdlib.h>' or provide a declaration of 'exit'
main.c: At top level:
main.c:45:1: warning: return type defaults to 'int' [-Wimplicit-int]
   45 | main(i){
      | ^~~~
main.c: In function 'main':
main.c:45:1: warning: type of 'i' defaults to 'int' [-Wimplicit-int]
main.c:46:9: warning: implicit declaration of function 'signal' [-Wimplicit-function-declaration]
   46 |         signal(14,ha);
      |         ^~~~~~
main.c:52:9: warning: implicit declaration of function 'scanf' [-Wimplicit-function-declaration]
   52 |         scanf("%d%lld",&n,&c);
      |         ^~~~~
main.c:52:9: note: include '<stdio.h>' or provide a declaration of 'scanf'
main.c:52:9: warning: incompatible implicit declaration of built-in function 'scanf' [-Wbuiltin-declaration-mismatch]
main.c:52:9: note: include '<stdio.h>' or provide a declaration of 'scanf'
main.c:56:9: warning: implicit declaration of function 'qsort' [-Wimplicit-function-declaration]
   56 |

ソースコード

diff # 

#include <sys/time.h>

typedef long long ll;
typedef struct{ll v,w,t,u;}S;

int n;
ll c;
ll b;
S ss[6000];

void ha(){
	printf("%lld\n",b);
	exit(0);
}

int sgn(double a){
	return a<0?-1:a>0;
}

int cmp(void*a,void*b){
	S*p=a,*q=b;
	return sgn((double)q->v/q->w-(double)p->v/p->w);
}

void dfs(int i,ll v,ll c){
	if(i==n){
		if(b<v){
			b=v;
		}
	}else{
		if(v+ss[i].t<=b){
			return;
		}
		if(c>=ss[i].w){
			dfs(i+1,v+ss[i].v,c-ss[i].w);
		}
		if(c<ss[i].u){
			dfs(i+1,v,c);
		}
	}
}

struct itimerval it;

main(i){
	signal(14,ha);
	//ualarm(1950000,0);
	it.it_value.tv_sec=1;
	it.it_value.tv_usec=950000;
	setitimer(ITIMER_REAL,&it,0);

	scanf("%d%lld",&n,&c);
	for(i=0;i<n;++i){
		scanf("%lld%lld",&ss[i].v,&ss[i].w);
	}
	qsort(ss,n,sizeof(S),cmp);

	ll t=0,u=0;
	for(i=n;i--;){
		ss[i].t=t+=ss[i].v;
		ss[i].u=u+=ss[i].w;
	}
	dfs(0,0ll,c);
	raise(14);
}
0