結果
問題 | No.798 コレクション |
ユーザー | Tiramister |
提出日時 | 2019-03-15 22:33:55 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 5,269 bytes |
コンパイル時間 | 1,195 ms |
コンパイル使用メモリ | 110,548 KB |
実行使用メモリ | 90,380 KB |
最終ジャッジ日時 | 2023-09-14 13:48:12 |
合計ジャッジ時間 | 5,043 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
8,752 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | AC | 1 ms
4,380 KB |
testcase_04 | AC | 1 ms
4,376 KB |
testcase_05 | AC | 1 ms
4,380 KB |
testcase_06 | AC | 2 ms
4,380 KB |
testcase_07 | AC | 2 ms
4,380 KB |
testcase_08 | AC | 2 ms
4,376 KB |
testcase_09 | AC | 1 ms
4,376 KB |
testcase_10 | AC | 1 ms
4,380 KB |
testcase_11 | AC | 1 ms
4,376 KB |
testcase_12 | AC | 2 ms
4,376 KB |
testcase_13 | TLE | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
ソースコード
// IO library #include <cstdio> #include <iomanip> #include <ios> #include <iostream> // algorithm library #include <algorithm> #include <cmath> #include <numeric> #include <random> // contancer library #include <bitset> #include <deque> #include <map> #include <queue> #include <set> #include <string> #include <tuple> #include <vector> using namespace std; using ll = long long; using ld = long double; template <class L, class R> ostream& operator<<(ostream& os, pair<L, R> p); template <class T> ostream& operator<<(ostream& os, vector<T> v) { os << "["; for (auto vv : v) os << vv << ","; return os << "]"; } template <class T> ostream& operator<<(ostream& os, set<T> v) { os << "{"; for (auto vv : v) os << vv << ","; return os << "}"; } template <class L, class R> ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.first << "," << p.second << ")"; } template <class K, class T> ostream& operator<<(ostream& os, map<K, T> v) { os << "{"; for (auto vv : v) os << vv << ","; return os << "}"; } template <class T> ostream& operator<<(ostream& os, queue<T> q) { os << "["; while (!q.empty()) { os << q.front() << ","; q.pop(); } return os << "]"; } template <class T> ostream& operator<<(ostream& os, priority_queue<T> q) { os << "{"; while (!q.empty()) { os << q.top() << ","; q.pop(); } return os << "}"; } const ll MOD = 1000000007; // const ll MOD = 998244353; // const int INF = 1 << 25; // const ll INF = 1LL << 50; // const ld PI = acos(-1); // const ld EPS = 1e-10; // mt19937 mt(ll(time(0))); template <class T> vector<T> Vec(size_t l, T v) { return vector<T>(l, v); } template <class T, class... Ts> auto Vec(size_t l, Ts... ts) { return vector<decltype(Vec<T>(ts...))>(l, Vec<T>(ts...)); } template <typename T> inline T sq(T a) { return a * a; } template <typename T> inline T iceil(T n, T d) { return (n + d - 1) / d; } template <typename T> T gcd(T a, T b) { while (b > 0) { a %= b; swap(a, b); } return a; } template <typename T, typename U> T ipow(T b, U n) { T ret = 1; while (n > 0) { if (n & 1) ret *= b; n >>= 1; b *= b; } return ret; } template <typename T, typename U> T mpow(T b, U n) { T ret = 1; while (n > 0) { if (n & 1) ret = ret * b % MOD; n >>= 1; b = b * b % MOD; } return ret; } struct edge { ll to; ll cap; ll cost; ll rev; // path[to]中でのfromのイテレータ edge(ll to_, ll cap_, ll cost_, ll rev_) : to(to_), cap(cap_), cost(cost_), rev(rev_){}; }; class MinCostFlow { public: explicit MinCostFlow(ll N) : MAX_V(N) { path.resize(MAX_V); } void add_edge(ll from, ll to, ll cap, ll cost) { // fromとtoの間に双方向の辺を加える // 有向の場合は後者のcapを0にする path[from].push_back(edge(to, cap, cost, path[to].size())); path[to].push_back(edge(from, 0, -cost, path[from].size() - 1)); } ll min_cost_flow(ll s, ll g, ll f) { // sからgへ流量fを流すときの最小コストを求める ll ret = 0; while (f > 0) { // Bellman-Fordでs-g間最短経路を求める vector<ll> d(MAX_V, INF), prevv(MAX_V), preve(MAX_V); d[s] = 0; while (true) { bool update = false; for (ll v = 0; v < MAX_V; ++v) { if (d[v] == INF) continue; for (ll i = 0; i < path[v].size(); ++i) { auto e = path[v][i]; if (e.cap > 0 && d[e.to] > d[v] + e.cost) { d[e.to] = d[v] + e.cost; prevv[e.to] = v; preve[e.to] = i; update = true; } } } if (!update) break; } // これ以上流せない if (d[g] == INF) break; ll sf = f, v = g; while (v != s) { sf = min(sf, path[prevv[v]][preve[v]].cap); v = prevv[v]; } f -= sf; ret += sf * d[g]; v = g; while (v != s) { auto& e = path[prevv[v]][preve[v]]; e.cap -= sf; path[v][e.rev].cap += sf; v = prevv[v]; } } return ret; } const ll INF = 1LL << 50; vector<vector<edge>> path; ll MAX_V; }; int main() { int N; cin >> N; int day = N - N / 3; vector<ll> A(N), B(N); for (int i = 0; i < N; ++i) { cin >> A[i] >> B[i]; } MinCostFlow mcf(day + N + 2); for (int d = 0; d < day; ++d) { mcf.add_edge(day + N + 1, d, 1, 0); } for (int d = 0; d < day; ++d) { for (int i = 0; i < N; ++i) { mcf.add_edge(d, day + i, 1, A[i] + B[i] * d); } } for (int i = 0; i < N; ++i) { mcf.add_edge(day + i, day + N, 1, 0); } cout << mcf.min_cost_flow(day + N + 1, day + N, day) << endl; return 0; }