結果
問題 |
No.2549 Paint Eggs
|
ユーザー |
|
提出日時 | 2023-10-25 13:42:34 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 183 ms / 2,000 ms |
コード長 | 5,008 bytes |
コンパイル時間 | 4,449 ms |
コンパイル使用メモリ | 142,532 KB |
実行使用メモリ | 11,316 KB |
最終ジャッジ日時 | 2024-09-25 05:51:17 |
合計ジャッジ時間 | 14,377 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 45 |
ソースコード
/*{{{ author: ryota2357 */ #include <algorithm> #include <cassert> #include <cmath> #include <iostream> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <string> #include <tuple> #include <utility> #include <vector> namespace ryota2357 { template <class T1, class T2> inline std::istream& operator>>(std::istream& is, std::pair<T1, T2>& P) noexcept { return is >> P.first >> P.second; } template <class T> inline std::istream& operator>>(std::istream& is, std::vector<T>& V) noexcept { for (auto& v : V) is >> v; return is; } template <class T> inline std::ostream& operator<<(std::ostream& os, const std::vector<T>& V) noexcept { const auto n = V.size() - 1; for (int i = 0; i < n; ++i) os << V[i] << ' '; return os << V.back(); } inline void IN(void) noexcept { return; } template <class T, class... U> inline void IN(T& t, U&... u) noexcept { std::cin >> t; IN(u...); } template <class T> inline void OUT(const T& x) noexcept { std::cout << x << '\n'; } template <class T> inline bool chmax(T& a, const T& b) noexcept { return a < b ? a = b, true : false; } template <class T> inline bool chmin(T& a, const T& b) noexcept { return a > b ? a = b, true : false; } template <class T = int> inline T read(void) { T ret = 0; char c = getchar(); while ((c < '0' || '9' < c) && c != '-') c = getchar(); const bool f = (c == '-') && (c = getchar()); while ('0' <= c && c <= '9') { ret = 10 * ret + c - '0'; c = getchar(); } return f ? -ret : ret; } template <class T> inline T ceil_div(const T& a, const T& b) { assert(b != 0); return (a + (b - 1)) / b; } template <class T> inline T max(const std::vector<T>& v) { return *max_element(v.begin(), v.end()); } template <class T> inline T min(const std::vector<T>& v) { return *min_element(v.begin(), v.end()); } template <class F> inline constexpr decltype(auto) recursive(F&& f) { return [f = std::forward<F>(f)](auto&&... args) { return f(f, std::forward<decltype(args)>(args)...); }; } } // namespace ryota2357 using ll = long long; using pint = std::pair<int, int>; #define rep(i, a, b) for (ll i = (a); i < ll(b); ++i) #define repr(i, a, b) for (ll i = (a); i >= ll(b); --i) #define each(x, v) for (auto& x : v) #define All(x) (x).begin(), (x).end() #define AllR(x) (x).rbegin(), (x).rend() #define Sort(x) (sort((x).begin(), (x).end())) #define SortR(x) (sort((x).rbegin(), (x).rend())) #define Unique(x) (x.erase(unique((x).begin(), (x).end()), (x).end())) #define Fill(v, n) (fill((v), (v) + sizeof(v) / sizeof(*(v)), (v))) #define INF (1073741823) #define INFL (2305843009213693951ll) using namespace std; using namespace ryota2357; /*}}}*/ template <class T, T (*op)(T, T), T e> struct SegmentTree { int _originSize, _size, _log2; vector<T> _data; SegmentTree(int size) : SegmentTree(vector<T>(size, e)) {} SegmentTree(const vector<T>& vec) : _originSize(vec.size()), _size(1), _log2(1) { while (_originSize > 1 << _log2) { ++_log2; } _size <<= _log2; _data = vector<T>(2 * _size, e); for (int i = 0; i < _originSize; ++i) { _data[i + _size] = vec[i]; } for (int i = _size - 1; i >= 1; --i) { _data[i] = op(_data[2 * i + 1], _data[2 * i]); } } void update(const int& index, const T value) { assert((uint)index < (uint)_size); int pos = index + _size; _data[pos] = value; for (int i = 1; i <= _log2; ++i) { int t = pos >> i; _data[t] = op(_data[2 * t + 1], _data[2 * t]); } } inline T get(const int& index) const { assert((uint)index < (uint)_size); return _data[index + _size]; } T query(const int& l, const int& r) const { assert(0 <= l && l <= r && r <= _size); int nl = l + _size; int nr = r + _size; T retl = e, retr = e; while (nl < nr) { if (nl & 1) { retl = op(retl, _data[nl]); ++nl; } if (nr & 1) { --nr; retr = op(retr, _data[nr]); } nl >>= 1; nr >>= 1; } return op(retl, retr); } }; ll min_op(ll a, ll b) { return min(a, b); } int main() { int n, m, k; IN(n, m, k); vector<int> c(n); vector<ll> a(m); IN(c, a); rep(i, 0, n) c[i] -= 1; SegmentTree<ll, min_op, INFL> st(m); rep(color, 0, m) { st.update(color, a[color] * k); } rep(i, 0, k) { int color = c[i]; st.update(color, st.get(color) - a[color]); } ll ans = st.query(0, m); rep(i, k, n) { int rm_color = c[i - k]; int in_color = c[i]; st.update(rm_color, st.get(rm_color) + a[rm_color]); st.update(in_color, st.get(in_color) - a[in_color]); chmin(ans, st.query(0, m)); } OUT(ans); return 0; }