結果
問題 | No.2623 Room Allocation |
ユーザー |
|
提出日時 | 2024-02-09 22:28:49 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 116 ms / 2,000 ms |
コード長 | 1,822 bytes |
コンパイル時間 | 950 ms |
コンパイル使用メモリ | 102,348 KB |
実行使用メモリ | 14,272 KB |
最終ジャッジ日時 | 2024-09-28 15:42:30 |
合計ジャッジ時間 | 3,603 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <iostream>#include <algorithm>#include <vector>using namespace std;using ll = long long;void solve (int N, int X, int Y, vector<pair<int, char>>& custemer) {// 面白い。最初の考察として、先頭X+Y人が大事になることがわかる。// なぜならi組目が部屋Aに割り当てられたとき、必ずX+Y+i組目も部屋Aに割り当てられるから。//// ここから、次の問題に帰着する。// 長さX+Yの数列A, Bが与えられる。// 長さXの部分列を{1, 2, ..., X+Y}からとり、pとする。// C[i] = A[i] (if i in p)// B[i] (if i not in p)// としたとき、Cの総和の最大値は?// これは次の考え方で解ける。// 最初全項Aにいたとして、Y項だけBに転落させる。// 総和の減少を最小にせよ。// これはA[i]-B[i]を持っておけば貪欲にとれて、ソート分のO((X+Y)log(X+Y))で解ける。vector<ll> A(X+Y), B(X+Y);for (int i = 0; i < X+Y; i++) {int cur = i;while (cur < N) {char c = custemer[cur].second;int P = custemer[cur].first;if (c == 'A') A[i] += P;if (c == 'B') B[i] += P;cur += X+Y;}}vector<ll> diff(X+Y);for (int i = 0; i < X+Y; i++) diff[i] = A[i]-B[i];sort(diff.begin(), diff.end());ll ans = 0;for (auto& a : A) ans += a;for (int i = 0; i < Y; i++) {ans -= diff[i];}cout << ans << "\n";}int main () {int N, X, Y; cin >> N >> X >> Y;vector<pair<int, char>> custemer(N);for (int i = 0; i < N; i++) {int P;char c;cin >> P >> c;custemer[i] = make_pair(P, c);}solve(N, X, Y, custemer);}