結果

問題 No.1430 Coup de Coupon
コンテスト
ユーザー mine691
提出日時 2021-03-14 13:47:51
言語 C++17(gcc12)
(gcc 12.4.0 + boost 1.90.0)
コンパイル:
g++-12 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
RE  
実行時間 -
コード長 2,371 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 7,626 ms
コンパイル使用メモリ 336,244 KB
実行使用メモリ 122,716 KB
最終ジャッジ日時 2026-06-18 18:36:26
合計ジャッジ時間 10,584 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other RE * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// Enjoy your stay. Code by evima

#include <atcoder/convolution>
#include <atcoder/dsu>
#include <atcoder/fenwicktree>
#include <atcoder/lazysegtree>
#include <atcoder/math>
#include <atcoder/maxflow>
#include <atcoder/mincostflow>
#include <atcoder/modint>
#include <atcoder/scc>
#include <atcoder/segtree>
#include <atcoder/string>
#include <atcoder/twosat>
#include "testlib.h"
using namespace atcoder;
using mint = modint998244353; // modint1000000007;// modint;

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

using ld = long double;
using ll = long long;
using lll = __int128;
using vl = vector<ll>;
using vs = vector<string>;
using LOOPVAR_TYPE = ll;

#define all(x) (x).begin(), (x).end()
#define sq(x) ((x) * (x))
#define sz(x) ll((x).size())
#define GET_MACRO(_1, _2, _3, NAME, ...) NAME
#define rep1(i, n) rep2(i, 0, n)
#define rep2(i, a, b) for (LOOPVAR_TYPE i = LOOPVAR_TYPE(a); i < LOOPVAR_TYPE(b); i++)
#define rep(...)                       \
	GET_MACRO(__VA_ARGS__, rep2, rep1) \
	(__VA_ARGS__)

const ld EPS = 1e-9;
const ld PI = 3.14159265358979323846L;
const ll INF = 1070;
const int M = 5000;
ll P[M], A[M], B[M], dp[M + 1][M + 1];

int main(int argc, char *argv[])
{
	registerValidation(argc, argv);
	// fast_io();

	int num_tc = 1;
	// cin >> num_tc;

	rep(tc, 1, num_tc + 1)
	{
		int C, N;
		cin >> N >> C;
		// inf.readSpace();
		// int C = inf.readInt(1, 5000);
		// inf.readEoln();
		rep(i, N) cin >> P[i];
		// rep(i, N)
		// {
		// 	P[i] = inf.readInt(100, 100000);
		// 	assert(P[i] % 100 == 0);
		// 	inf.readEoln();
		// }
		sort(P, P + N, greater<ll>());
		int ia = 0, ib = 0;
		// rep(i, C)
		// {
		// 	int T = inf.readInt(0, 1);
		// 	inf.readSpace();
		// 	int X;
		// 	if (T == 1)
		// 	{
		// 		X = inf.readInt(1, 100000);
		// 		A[ia++] = X;
		// 	}
		// 	else
		// 	{
		// 		X = inf.readInt(1, 100);
		// 		B[ib++] = X;
		// 	}
		// 	inf.readEoln();
		// }
		rep(i, C)
		{
			ll T, X;
			cin >> T >> X;
			if (T == 1)
				A[ia++] = X;
			else
				B[ib++] = X;
		}
		sort(A, A + ia, greater<ll>());
		sort(B, B + ib, greater<ll>());
		for (int i = N; i >= 0; --i)
		{
			rep(j, i + 1)
			{
				if (i == N)
					dp[i][j] = 0;
				else
				{
					ll p1 = max(0LL, P[i] - A[j]) + dp[i + 1][j + 1];
					ll p2 = P[i] * (100 - B[i - j]) / 100 + dp[i + 1][j];
					dp[i][j] = min(p1, p2);
				}
			}
		}
		cout << dp[0][0] << endl;
	}
}
0