#910639 (C++23) No.1858 Gorgeous Knapsack

• 問題: No.1858 Gorgeous Knapsack
• ユーザー: Ayush Gangwani
• 提出日時: 2023-09-02 18:57:23
• 言語: C++23 (gcc 12.3.0 + boost 1.83.0)
• 結果: WA
• 実行時間: -
• コード長: 1,038 bytes
• コンパイル時間: 3,837 ms
• コンパイル使用メモリ: 255,472 KB
• 実行使用メモリ: 199,168 KB
• 最終ジャッジ日時: 2024-06-12 01:24:15
• 合計ジャッジ時間: 7,261 ms
• ジャッジサーバーID （参考情報）: judge5 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	3 ms; 5,376 KB
testcase_04	AC	47 ms; 40,832 KB
testcase_05	AC	11 ms; 10,496 KB
testcase_06	AC	55 ms; 49,408 KB
testcase_07	AC	33 ms; 29,184 KB
testcase_08	AC	79 ms; 69,632 KB
testcase_09	AC	135 ms; 117,376 KB
testcase_10	AC	38 ms; 32,128 KB
testcase_11	AC	63 ms; 55,168 KB
testcase_12	AC	104 ms; 91,904 KB
testcase_13	AC	11 ms; 8,320 KB
testcase_14	AC	2 ms; 5,376 KB
testcase_15	AC	2 ms; 5,376 KB
testcase_16	AC	2 ms; 5,376 KB
testcase_17	AC	2 ms; 5,376 KB
testcase_18	AC	2 ms; 5,376 KB
testcase_19	AC	2 ms; 5,376 KB
testcase_20	AC	2 ms; 5,376 KB
testcase_21	WA	-
testcase_22	AC	2 ms; 5,376 KB
testcase_23	WA	-
testcase_24	AC	19 ms; 17,920 KB
testcase_25	AC	98 ms; 85,376 KB
testcase_26	AC	78 ms; 68,864 KB
testcase_27	AC	77 ms; 66,176 KB
testcase_28	AC	53 ms; 46,080 KB
testcase_29	AC	4 ms; 5,376 KB
testcase_30	AC	4 ms; 5,376 KB
testcase_31	AC	5 ms; 5,376 KB
testcase_32	AC	4 ms; 5,376 KB
testcase_33	AC	6 ms; 5,376 KB
testcase_34	WA	-
testcase_35	AC	221 ms; 199,040 KB
testcase_36	AC	228 ms; 199,040 KB
testcase_37	AC	3 ms; 5,376 KB
testcase_38	WA	-
testcase_39	WA	-
testcase_40	AC	222 ms; 199,040 KB

ソースコード

#include<bits/stdc++.h>
using namespace std;

long findMaxEfficiency(int m, vector<int> values, vector<int> resources) {
    int n = values.size();
	vector<int> order(n); 
	iota(order.begin(),order.end(),0);
	sort(order.begin(),order.end(), [&](const int& l, const int& r){
		return values[l] > values[r];
	});
	vector<vector<int>> dp0(n, vector<int> (m+1,0)), dp1(n, vector<int> (m+1,0));
    dp1[0][resources[order[0]]] = values[order[0]];
    for(int i=1; i<n; i++){
		for(int j=1; j<=m; j++){
			dp1[i][j] = dp1[i][j-1];
		    dp0[i][j] = max({dp0[i][j-1], dp0[i-1][j], dp1[i-1][j]});
			if(resources[order[i]] <= j) dp1[i][j] = max(dp1[i][j-1], values[order[i]] + max(dp0[i-1][j-resources[order[i]]], dp1[i-1][j-resources[order[i]]]));  	
	    }
	}	
	long ans = 0;
    for(int i=0; i<n; i++) ans = max(ans, 1L*values[order[i]]*dp1[i][m]);
	return ans;
}

int main(){
	int n,m; cin>>n>>m;
	vector<int> values(n), resources(n);
	for(int i=0; i<n; i++) cin>>values[i]>>resources[i];
	cout<<findMaxEfficiency(m,values,resources)<<"\n";
}