結果

問題 No.54 Happy Hallowe'en
ユーザー tottoripapertottoripaper
提出日時 2015-03-24 15:32:27
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 315 ms / 5,000 ms
コード長 2,147 bytes
コンパイル時間 483 ms
コンパイル使用メモリ 43,748 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-15 17:11:17
合計ジャッジ時間 3,078 ms
ジャッジサーバーID
(参考情報)
judge4 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 19
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:107:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  107 |     scanf("%d", &N);
      |     ~~~~~^~~~~~~~~~
main.cpp:110:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  110 |         scanf("%d %d", V+i, T+i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

ソースコード

diff #
プレゼンテーションモードにする

// Wrongri-La Shower
#include <cstdio>
#include <algorithm>
#include <utility>
typedef std::pair<int,int> P;
typedef std::pair<int,P> Q;
int N;
int V[10000], T[10000];
int dp[1<<12][20001];
int solve(){
Q ps[10000];
for(int i=0;i<N;i++){
ps[i] = std::make_pair(T[i]+V[i], std::make_pair(T[i], V[i]));
}
std::sort(ps, ps+N);
std::reverse(ps, ps+N);
int mx[20001];
for(int i=0;i<=20000;i++){
mx[i] = i;
}
for(int i=0;i<N;i++){
// printf("[%d, %d\n", i, ps[i].second);
const P& p = ps[i].second;
for(int j=0;j<=20000;j++){
if(j-p.second < 0){continue;}
if(j < p.first || j-p.second < p.first){
mx[j-p.second] = std::max(mx[j-p.second], mx[j]);
}
}
// puts(std::string(40, '-').c_str());
// for(int j=0;j<110;j++){
// printf("%d: %d\n", j, mx[j]);
// }
}
return mx[0];
}
int rec(int state, int sum){
if(dp[state][sum] != -1){return dp[state][sum];}
int res = sum;
for(int i=0;i<N;i++){
if(state >> i & 1){continue;}
if(sum >= T[i]){continue;}
res = std::max(res, rec(state | (1 << i), sum + V[i]));
}
return dp[state][sum] = res;
}
// bitDP ()
int solve1(){
for(int i=0;i<1<<N;i++){
for(int j=0;j<=20000;j++){
dp[i][j] = -1;
}
}
return rec(0, 0);
}
// T[i] ()
int solve2(){
P ps[10000];
for(int i=0;i<N;i++){
ps[i] = std::make_pair(T[i], V[i]);
}
std::sort(ps, ps+N);
int sum = 0;
for(int i=0;i<N;i++){
if(sum < ps[i].first){sum += ps[i].second;}
}
return sum;
}
// V[i] ()
int solve3(){
P ps[10000];
for(int i=0;i<N;i++){
ps[i] = std::make_pair(V[i], T[i]);
}
std::sort(ps, ps+N);
int sum = 0;
for(int i=0;i<N;i++){
if(sum < ps[i].second){sum += ps[i].first;}
}
return sum;
}
int main(){
scanf("%d", &N);
for(int i=0;i<N;i++){
scanf("%d %d", V+i, T+i);
}
printf("%d\n", solve());
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0