結果

問題 No.1583 Building Blocks
コンテスト
ユーザー rin204
提出日時 2022-01-26 23:20:05
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
MLE  
実行時間 -
コード長 742 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,741 ms
コンパイル使用メモリ 178,812 KB
実行使用メモリ 1,553,000 KB
最終ジャッジ日時 2024-12-23 19:31:17
合計ジャッジ時間 76,609 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 MLE * 2
other AC * 7 TLE * 17 MLE * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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