結果
問題 | No.2492 Knapsack Problem? |
ユーザー |
|
提出日時 | 2023-10-06 22:30:36 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 648 bytes |
コンパイル時間 | 1,757 ms |
コンパイル使用メモリ | 174,272 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-26 16:37:47 |
合計ジャッジ時間 | 2,361 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 9 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> P; #define REP(i,n) for(int i=0;i<int(n);i++) int main(void){ cin.tie(nullptr); ios_base::sync_with_stdio(false); int i,j,k; int N,W; cin >> N >> W; vector<P> a(N); for(i=0;i<N;i++){ int v,w; cin >> v >> w; a[i].first=w; a[i].second=v; } sort(a.begin(),a.end()); int p=-1; for(i=N-1;i>=0;i--){ if(a[i].first<=W){ p=i; break; } } if(p==-1){ cout << -1 << endl; return 0; } int mx=0,q=-1; for(i=0;i<=p;i++){ if(mx<a[i].second){ mx=a[i].second; q=i; } } cout << a[q].second << endl; return 0; }