結果

問題 No.1430 Coup de Coupon
ユーザー mine691mine691
提出日時 2021-03-14 13:50:16
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 118 ms / 2,000 ms
コード長 4,924 bytes
コンパイル時間 4,343 ms
コンパイル使用メモリ 266,028 KB
最終ジャッジ日時 2025-01-19 16:28:53
ジャッジサーバーID
（参考情報） 		judge4 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

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>
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__)

#define eb emplace_back
#define fir first
#define sec second
#define mp make_pair
#define mt make_tuple

const ld EPS = 1e-9;
const ld PI = 3.14159265358979323846L;
const ll INF = 1070000000LL;
const ll MOD = 998244353LL; // 1000000007LL;

void fast_io()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
}
ll lin()
{
	ll x;
	cin >> x;
	return x;
}
string input()
{
	string s;
	cin >> s;
	return s;
}
vl vin(int n)
{
	vector<ll> v(n);
	rep(i, n) cin >> v[i];
	return v;
}
template <typename T>
bool chmin(T &a, const T &b) { return (b < a) ? (a = b, true) : false; }
template <typename T>
bool chmax(T &a, const T &b) { return (a < b) ? (a = b, true) : false; }
template <typename T>
map<T, ll> freq(const vector<T> &v)
{
	map<T, ll> ret;
	for (T x : v)
		++ret[x];
	return ret;
}
template <typename T>
vector<T> reversed(vector<T> v)
{
	reverse(all(v));
	return v;
}
template <typename T>
vector<T> sorted(vector<T> v)
{
	sort(all(v));
	return v;
}
template <typename T>
vector<T> sub(const vector<T> &v, int from, int to)
{
	vector<T> ret;
	copy(&v[from], &v[to], back_inserter(ret));
	return ret;
}
template <typename T>
string str(const T &x)
{
	stringstream ss;
	ss << x;
	return ss.str();
}
template <typename Tuple, size_t... I>
array<int, sizeof...(I)> str_tuple_impl(stringstream &ss, Tuple &&t, index_sequence<I...>) { return {{(void(ss << str(get<I>(t)) << " "), 0)...}}; }
template <typename Tuple>
string str_tuple(Tuple &&t)
{
	stringstream ss;
	str_tuple_impl(ss, forward<Tuple>(t), make_index_sequence<tuple_size<decay_t<Tuple>>::value>{});
	string s = ss.str();
	if (s.size() > 0)
		s.pop_back();
	return s;
}
template <typename T, typename U>
string str(const pair<T, U> &p) { return str_tuple(p); }
template <typename... T>
string str(const tuple<T...> &t) { return str_tuple(t); }
template <typename T>
string str(const vector<T> &v)
{
	stringstream ss;
	rep(i, sz(v)) ss << v[i] << (i < sz(v) - 1 ? " " : "");
	return ss.str();
}
template <typename T>
void print1(T &&x, const string &end) { cout << str(x) << end; }
void print() { print1("", "\n"); }
template <typename T, typename... U>
void print(T &&head, U &&...tail)
{
	print1(head, " ");
	print(forward<U>(tail)...);
}
template <typename T>
void eprint1(T &&x, const string &end) { cerr << str(x) << end; }
void eprint() { eprint1("", "\n"); }
template <typename T, typename... U>
void eprint(T &&head, U &&...tail)
{
	eprint1(head, " ");
	eprint(forward<U>(tail)...);
}
template <typename... T>
void quit(T &&...x)
{
	print(forward<T>(x)...);
	exit(0);
}
template <typename T, typename U>
void yn(bool cnd, T &&yes = "Yes", U &&no = "No")
{
	if (cnd)
		print(yes);
	else
		print(no);
}
void zip(vl &v)
{
	vl w = v;
	sort(all(w));
	int n = unique(all(w)) - w.begin();
	for (ll &x : v)
		x = lower_bound(&w[0], &w[n], x) - &w[0];
}
vl zipped(vl v)
{
	zip(v);
	return v;
}
map<ll, ll> zipmap(vl v)
{
	map<ll, ll> ret;
	sort(all(v));
	v.erase(unique(all(v)), v.end());
	rep(i, sz(v)) ret[v[i]] = i;
	return ret;
}

const int M = 5000;
int N, C;
ll P[M], A[M], B[M], dp[M + 1][M + 1];

void solveOne()
{
	cin >> N >> C;
	assert(1 <= N and N <= 5000);
	assert(1 <= C and C <= 5000);
	rep(i, N)
	{
		cin >> P[i];
		assert(P[i] % 100 == 0);
		assert(1 <= P[i] and P[i] <= 100000);
	}
	sort(P, P + N, greater<ll>());
	int ia = 0, ib = 0;
	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);
			}
		}
	}
	print(dp[0][0]);
}

int main()
{
	fast_io();
	cout << setprecision(20);

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

	rep(tc, 1, num_tc + 1)
	{
		// cout << "Case #" << tc << ": " ;// << endl;
		solveOne();
	}
}
0