結果

問題 No.1430 Coup de Coupon
ユーザー mine691mine691
提出日時 2021-03-14 13:47:51
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 2,371 bytes
コンパイル時間 11,141 ms
コンパイル使用メモリ 336,620 KB
実行使用メモリ 162,508 KB
最終ジャッジ日時 2024-11-06 03:29:15
合計ジャッジ時間 12,985 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

// 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