結果

問題 No.527 ナップサック容量問題
ユーザー ei1333333
提出日時 2017-06-09 22:30:50
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 15 ms / 2,000 ms
コード長 801 bytes
コンパイル時間 1,246 ms
コンパイル使用メモリ 158,796 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-22 15:15:52
合計ジャッジ時間 2,595 ms
ジャッジサーバーID
(参考情報)
judge3 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

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

#include<bits/stdc++.h>
using namespace std;
typedef long long int64;
int main()
{
int N, V;
int dp[100002];
fill_n(dp, 100002, -1);
dp[0] = 0;
cin >> N;
for(int i = 0; i < N; i++) {
int v, k;
cin >> v >> k;
for(int j = 100001 - k; j >= 0; j--) {
if(dp[j] == -1) continue;
dp[j + k] = max(dp[j + k], dp[j] + v);
}
}
cin >> V;
int ret = 0;
for(int j = 1; j <= 100001; j++) {
dp[j] = max(dp[j], dp[j - 1]);
}
int latte = 11451419, malta = -11451419;
for(int i = 1; i < 100002; i++) {
if(dp[i] == V) {
latte = min(latte, i);
malta = max(malta, i);
}
}
if(latte >= 11451419) cout << "inf" << endl;
else cout << latte << endl;
if(malta < 0 || malta >= 100001) cout << "inf" << endl;
else cout << malta << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0