結果
| 問題 | No.3023 Utility is Max? |
| ユーザー |
 hirakuuuu
|
| 提出日時 | 2025-02-14 23:05:59 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 523 ms / 1,000 ms |
| コード長 | 5,945 bytes |
| コンパイル時間 | 3,678 ms |
| コンパイル使用メモリ | 279,468 KB |
| 実行使用メモリ | 6,824 KB |
| 最終ジャッジ日時 | 2025-02-14 23:06:12 |
| 合計ジャッジ時間 | 13,166 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 17 |
ソースコード
#include <bits/stdc++.h>// #include <atcoder/all>using namespace std;// using namespace atcoder;#define rep(i, a, n) for(int i = a; i < n; i++)#define rrep(i, a, n) for(int i = a; i >= n; i--)#define inr(l, x, r) (l <= x && x < r)#define ll long long#define ld long double// using mint = modint1000000007;// using mint = modint998244353;constexpr int IINF = 1001001001;constexpr ll INF = 1e18;template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}// 最大フロー問題を解くためのアルゴリズムtemplate <class Cap>class Dinic {int _n;struct _edge {int to, rev;Cap cap;};vector<pair<int, int>> pos;vector<vector<_edge>> g;public:Dinic(): _n(0) {}explicit Dinic(int n): _n(n), g(n) {}int add_edge(int from, int to, Cap cap){assert(0 <= from && from < _n);assert(0 <= to && to < _n);assert(0 <= cap);int m = (int)pos.size();pos.push_back({from, (int)g[from].size()});int from_id = (int)g[from].size();int to_id = (int)g[to].size();if(from == to) to_id++;g[from].push_back(_edge{to, to_id, cap});g[to].push_back(_edge{from, from_id, 0});return m;}struct edge{int from, to;Cap cap, flow;};edge get_edge(int i){int m = (int)pos.size();assert(0 <= i && i < m);auto _e = g[pos[i].first][pos[i].second];auto _re = g[_e.to][_e.rev];return edge{pos[i].first, _e.to, _e.cap+_re.cap, _re.cap};}vector<edge> edges(){int m = (int)pos.size();vector<edge> result;for(int i = 0; i < m; i++){result.push_back(get_edge(i));}return result;}void change_edge(int i, Cap new_cap, Cap new_flow){int m = (int)pos.size();assert(0 <= i && i < m);assert(0 <= new_flow && new_flow <= new_cap);auto& _e = g[pos[i].first][pos[i].second];auto& _re = g[_e.to][_e.rev];_e.cap = new_cap-new_flow;_re.cap = new_flow;}Cap flow(int s, int t){return flow(s, t, numeric_limits<Cap>::max());}// s!=t である必要ありCap flow(int s, int t, Cap flow_limit){assert(0 <= s && s < _n);assert(0 <= t && t < _n);assert(s != t);vector<int> level(_n), iter(_n);queue<int> que;auto bfs = [&]()->void {fill(level.begin(), level.end(), -1);level[s] = 0;queue<int>().swap(que);que.push(s);while(!que.empty()){int v = que.front(); que.pop();for(auto e: g[v]){if(e.cap == 0 || level[e.to] >= 0) continue;level[e.to] = level[v]+1;if(e.to == t) return;que.push(e.to);}}};auto dfs = [&](auto self, int v, Cap up)->Cap {if(v == s) return up;Cap res = 0;int level_v = level[v];for(int& i = iter[v]; i < (int)g[v].size(); i++){_edge& e = g[v][i];if(level_v <= level[e.to] || g[e.to][e.rev].cap == 0) continue;Cap d = self(self, e.to, min(up-res, g[e.to][e.rev].cap));if(d <= 0) continue;g[v][i].cap += d;g[e.to][e.rev].cap -= d;res += d;if(res == up) return res;}level[v] = _n;return res;};Cap flow = 0;while(flow < flow_limit){bfs();if(level[t] == -1) break;fill(iter.begin(), iter.end(), 0);Cap f = dfs(dfs, t, flow_limit-flow);if(!f) break;flow += f;}return flow;}// 最小カットをした上で、頂点 s 側に属する頂点集合を返すvector<bool> min_cut(int s){vector<bool> visited(_n);queue<int> que;while(!que.empty()){int p = que.front(); que.pop();visited[p] = true;for(auto e: g[p]){if(e.cap && !visited[e.to]){visited[e.to] = true;que.push(e.to);}}}return visited;}};int main(){int q; cin >> q;while(q--){ll l; cin >> l;vector<ll> a(2), b(2), x(2), y(2);rep(i, 0, 2){cin >> a[i] >> b[i] >> x[i] >> y[i];}// 購入可能かどうかと，予算をちょうど使い切るかbool ok = true;rep(i, 0, 2){if(a[i]*x[i]+b[i]*y[i] == l) continue;ok = false;break;}if(!ok){cout << "No" << endl;continue;}// // 入れ替えて，各々条件を満たさないならOK// if(max(a[0]*x[1]+b[0]*y[1], a[1]*x[0]+b[1]*y[0]) <= l){// cout << "Yes" << endl;// continue;// }// 入れ替えても OK な場合を検証ok = true;rep(i, 0, 2){if(a[i]*x[1-i]+b[i]*y[1-i] <= l){// i = 0 の場合を書く// f(x[0], y[0]) <= f(x[1], y[1]) が成り立つif(a[1-i]*x[i]+b[1-i]*y[i] < l){// (z, y[1]) (x[1] < z) が店 0 の条件を満たすので，// f(z, y[1]) <= f(x[0], y[0]) が成り立つ// f(x[1], y[1]) < f(z, y[1]) も成り立つので矛盾ok = false;break;}}}if(ok) cout << "Yes" << endl;else cout << "No" << endl;}return 0;}