結果
問題 | No.545 ママの大事な二人の子供 |
ユーザー |
|
提出日時 | 2020-10-21 11:21:37 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 8 ms / 2,000 ms |
コード長 | 2,230 bytes |
コンパイル時間 | 1,338 ms |
コンパイル使用メモリ | 131,416 KB |
最終ジャッジ日時 | 2025-01-15 12:13:30 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:63:21: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 63 | int n; scanf("%d", &n); | ~~~~~^~~~~~~~~~ main.cpp:64:65: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 64 | vector<ll> a(n), b(n); for (int i = 0; i < n; i++) scanf("%lld %lld", &a[i], &b[i]); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include <cstdio>#include <iostream>#include <string>#include <sstream>#include <stack>#include <algorithm>#include <cmath>#include <queue>#include <map>#include <set>#include <cstdlib>#include <bitset>#include <tuple>#include <assert.h>#include <deque>#include <bitset>#include <iomanip>#include <limits>#include <chrono>#include <random>#include <array>#include <unordered_map>#include <functional>#include <complex>#include <numeric>template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }//constexpr long long MAX = 5100000;constexpr long long INF = 1LL << 60;constexpr int inf = 1000000007;constexpr long long mod = 1000000007LL;//constexpr long long mod = 998244353LL;const long double PI = acos((long double)(-1));using namespace std;typedef unsigned long long ull;typedef long long ll;typedef long double ld;vector<ll> BruteForce(vector<ll>& a, vector<ll>& b) {int n = a.size();vector<ll> res; res.emplace_back(0);for (int i = 0; i < n; i++) {vector<ll> cur1;vector<ll> cur2;for (auto p : res) {cur1.emplace_back(p - b[i]);cur2.emplace_back(p + a[i]);}res.clear(); res.resize(cur1.size() + cur2.size());merge(cur1.begin(), cur1.end(), cur2.begin(), cur2.end(), res.begin());}return res;}int main(){/*cin.tie(nullptr);ios::sync_with_stdio(false);*/int n; scanf("%d", &n);vector<ll> a(n), b(n); for (int i = 0; i < n; i++) scanf("%lld %lld", &a[i], &b[i]);vector<ll> v1, v2;{int h = n / 2;vector<ll> ta1, tb1, ta2, tb2;ta1.reserve(h), tb1.reserve(h), ta2.reserve(n - h), tb2.reserve(n - h);for (int i = 0; i < h; i++) ta1.emplace_back(a[i]), tb1.emplace_back(b[i]);for (int i = h; i < n; i++) ta2.emplace_back(a[i]), tb2.emplace_back(b[i]);v1 = move(BruteForce(ta1, tb1));v2 = move(BruteForce(ta2, tb2));}int cur = 0;ll res = INF;for (int i = (int)v1.size() - 1; i >= 0; i--) {while (cur < v2.size() and v1[i] + v2[cur] < 0) cur++;if (cur) chmin(res, -(v1[i] + v2[cur - 1]));if (cur < v2.size()) chmin(res, v1[i] + v2[cur]);}cout << res << endl;return 0;}