結果
問題 |
No.2770 Coupon Optimization
|
ユーザー |
|
提出日時 | 2024-06-02 22:19:45 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 438 ms / 3,000 ms |
コード長 | 1,640 bytes |
コンパイル時間 | 4,362 ms |
コンパイル使用メモリ | 255,584 KB |
最終ジャッジ日時 | 2025-02-21 19:21:33 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 16 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> #include <iostream> #include <iomanip> #include <math.h> #include <random> #include <chrono> #include <cstdint> using namespace std; using namespace atcoder; // using mint = modint998244353; using mint = modint1000000007; using vi = vector<int>; using vvi = vector<vector<int>>; using ll = long long; template <class T> using max_heap = priority_queue<T>; template <class T> using min_heap = priority_queue<T, vector<T>, greater<>>; #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define rep2(i, f, n) for (int i = (int) f; i < (int)(n); i++) #define repd(i, n, l) for (int i = (int) n; i >= (int) l; i--) #define all(p) p.begin(),p.end() vector<pair<int, int>> dydx{{-1, 0}, {1, 0}, {0, -1 }, {0, 1}}; const ll inf = 1LL << 60; ll op(ll a,ll b) {return a+b;} ll e() {return 0LL;} int main() { int n, m; cin >> n >> m; vector<ll> A(n+1); vector<int> B(101, 0); rep(i, n){ ll a; cin >> a; a /= 100; A[i+1] = a; } A[0] = 0; sort(all(A)); rep(i, n) A[i+1] += A[i]; rep(i, m){ int b; cin >> b; B[100-b]++; } B[100] = 1000000; // segtree<ll, op, e> seg(A); for (int i = 1; i <= n; i++){ ll now = i; ll ans = 0; for (int j = 1; j <= 100; j++){ ll d = B[j]; if (d == 0) continue; ll left = max(0LL, now-d); ans += j * (A[now] - A[left]); // cout << ans << ' ' << now << ' ' << left << endl; now = left; if (now == 0) break; } cout << ans << endl; } return 0; }