BOJ 14728-稲妻爆破

タイムアウトメモリ制限正解の発行正解正解正解正解正解率2秒256 MB 23049876542.359%

質問する

俊碩は校長になって、仕事が多くなって、試験期間も仕事でよく勉強できなかったので、試験の前日に終わった.幸いなことに、親切な教授は試験前に以下のヒントを発表した.内容は以下の通り.

の複数のユニットを融合させる問題は出ない.

1ユニットで問題を出します.しかし、そのユニットですべての内容を知ってこそ、解答できる問題です.

この2つのヒントに伴い,各セルの配分が書かれている.あるユニットの質問に答えるために、そのユニットの予想学習時間がいくらであるか、あるいは学習時間がそのユニットより多ければ、正解することができる.そんな折、CHOS会長のことで苦労したジュンソクのために、残りの時間に勉強して最大点数を取る番組を作りました.

入力

1行目は,今回の試験のユニット数N(1≦N≦100)と,試験まで学習できる総時間T(1≦T≦10000)との間の空白を与えた.
2行目からN行目では、各セルの予想学習時間K(1≦K≦1000)とそのセル問題の配分S(1≦S≦1000)との間にスペースが残る.

しゅつりょく

1行目はジュンソクが得られる最大点数を出力する.

に近づく

これは普通のリュックサックの問題です.
時間をidxに、点数をvalueに置きます.

に答える

dp[T]を出力します.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };

int N, T, K, S, dp[10001];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	CIN2(N, T);
	FUP(i, 1, N)
	{
		CIN2(K, S);
		FDOWN(j, T, K)
		{
			dp[j] = max(dp[j], dp[j - K] + S);
		}
	}
	COUT(dp[T]);

	return 0;
}