結果
問題 | No.626 Randomized 01 Knapsack |
ユーザー |
![]() |
提出日時 | 2017-12-18 19:32:55 |
言語 | C (gcc 13.3.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 752 bytes |
コンパイル時間 | 274 ms |
コンパイル使用メモリ | 30,080 KB |
実行使用メモリ | 15,816 KB |
最終ジャッジ日時 | 2024-12-16 00:26:00 |
合計ジャッジ時間 | 55,799 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 7 TLE * 18 |
コンパイルメッセージ
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 <signal.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 <signal.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:44:1: warning: return type defaults to 'int' [-Wimplicit-int] 44 | main(i){ | ^~~~ main.c: In function 'main': main.c:44:1: warning: type of 'i' defaults to 'int' [-Wimplicit-int] main.c:46:9: warning: implicit declaration of function 'ualarm' [-Wimplicit-function-declaration] 46 | ualarm(1800000,0); | ^~~~~~ main.c:48:9: warning: implicit declaration of function 'scanf' [-Wimplicit-function-declaration] 48 | scanf("%d%lld",&n,&c); | ^~~~~ main.c:48:9: note: include '<stdio.h>' or provide a declaration of 'scanf' main.c:48:9: warning: incompatible implicit declaration of built-in function 'scanf' [-Wbuiltin-declaration-mismatch] main.c:48:9: note: include '<stdio.h>' or provide a declaration of 'scanf' main.c:52:9: warning: implicit declaration of function 'qsort' [-Wimplicit-function-declaration] 52 |
ソースコード
#include <signal.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); } } } main(i){ signal(14,ha); ualarm(1800000,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); }