BOJ 2515展示室

タイムアウトメモリ制限正解の送信正解正解正解正解率1秒256 MB 34291077541.814%

質問する

展示室では、絵を売る単位にブースが配置されています.表示する画像が矩形の形状を有すると仮定すると、画像の高さは異なるが、幅は同じである可能性がある.どの絵にも値段をつける.

メーカーは見学者に写真を見せるために、写真をブースに置いて、ブースの幅は写真の幅と同じで、重ねなければなりません.例えば、上図は、ブース上に4枚の図A、B、C、DがC、B、A、Dの順に重ねられている場合を示している.
上図の右半分は横に表示された画像のレイアウトを示し、左半分は前に配置された画像を見て見学者に見せる様子を示しています.図Aは前の図Bに隠されていて、見学者には全く見えず、一部の図でもB、C、Dしかありません.
視聴者が興味を持って購入するのは、見える部分の縦方向の長さが特定の整数S以上の絵だけだと仮定します.展示されている絵の中で、見える部分の縦の長さがSより大きい絵を販売可能な絵と呼んでいます.
画像の高さと価格を指定する場合は、画像を配置するときに販売可能な画像の最大値を求めるプログラムを作成します.

入力

1行目において、図の個数N(1<=N<=300000)は、販売可能な図を定義する1または複数の整数Sから1つのスペースを隔てている.次のN行では、1枚の絵の高さと価格を表す整数HとCがスペースを隔てて与えられる.しかし,1≦S≦H≦200000,1≦C≦1000であった.

しゅつりょく

1行目で、販売可能な画像の価格の合計を最大値に設定すると、その最大値が出力されます.

に近づく

これはこの探索を加えた簡単なDP問題である.
テーブルは今回の高さ-S+今回の価格、i-1回の価格の中から最安値を選べばいいです.

に答える

高さ順に絵を並べ替えます.
また、ツアーのたびにupper bound roheight[i]-Sのインデックスが検索されます.
点火式をコードで入れたら終わりです.

#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, S, dp[300001];
pair<int, int> arr[300001];
vector<int> height, price;


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

	arr[0] = { 0, 0 };
	MS(dp, 0);
	CIN2(N, S);
	FUP(i, 1, N) CIN2(arr[i].first, arr[i].second);
	sort(arr, arr + N + 1);
	FUP(i, 0, N)
	{
		height.push_back(arr[i].first);
		price.push_back(arr[i].second);
	}
	FUP(i, 1, N)
	{
		if (height[i] < S) continue;
		int idx = upper_bound(ALL(height), height[i] - S) - height.begin() - 1;
		dp[i] = max(dp[i - 1], dp[idx] + price[i]);
	}
	COUT(dp[N]);

	return 0;
}