結果

問題 No.1583 Building Blocks
コンテスト
ユーザー rin204
提出日時 2022-01-26 23:19:13
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 742 bytes
コンパイル時間 4,058 ms
コンパイル使用メモリ 206,924 KB
最終ジャッジ日時 2025-01-27 15:30:42
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 MLE * 1
other AC * 7 TLE * 16 MLE * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

int main(){
	int n;
	cin >> n;
	vector<vector<long long>> wsv(n, vector<long long>(3));
	for(int i = 0; i < n; i++){
		cin >> wsv[i][1] >> wsv[i][2];
		wsv[i][0] = wsv[i][1] + wsv[i][2];
	}
	sort(wsv.begin(), wsv.end());
	vector<long long> dp = {0LL};
	long long w, s, v;
	for(auto tmp: wsv){
		w = tmp[1];
		s = tmp[2];
		v = 1;
		vector<long long> dp2(s + w + 1, 0);
		int l = dp.size();
		for(int i = 1; i <= s + w; i++){
			dp2[i] = dp2[i - 1];
			if(i < l) dp2[i] = max(dp2[i], dp[i]);
			if(i >= w && i - w < l) dp2[i] = max(dp2[i], dp[i - w] + v);
		}
		dp.resize(s + w + 1);
		for(int i = 0; i <= s + w; i++) dp[i] = dp2[i];
	}
	int l = dp.size();
	cout << dp[l - 1] << "\n";
	return 0;
}
0