結果
問題 | No.2495 Three Sets |
ユーザー |
![]() |
提出日時 | 2023-10-06 22:52:49 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,607 ms / 3,000 ms |
コード長 | 3,959 bytes |
コンパイル時間 | 1,975 ms |
コンパイル使用メモリ | 210,176 KB |
最終ジャッジ日時 | 2025-02-17 05:26:32 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h>using namespace std;const int MAX = 3000;const long long INF = 1000000000000000000;template <typename T>struct li_chao_tree{struct line{T a, b;line(): a(0), b(INF){}line(T a, T b): a(a), b(b){}T get(T x){return a * x + b;}};int N;vector<T> x;vector<line> ST;li_chao_tree(const vector<T> &x2){x = x2;sort(x.begin(), x.end());int N2 = x.size();N = 1;while (N < N2){N *= 2;}x.resize(N);for (int i = N2; i < N; i++){x[i] = x[N2 - 1];}ST = vector<line>(N * 2 - 1);}void line_add(line L, int i, int l, int r){T la = L.get(x[l]);T lb = ST[i].get(x[l]);T ra = L.get(x[r - 1]);T rb = ST[i].get(x[r - 1]);if (la >= lb && ra >= rb){return;} else if (la <= lb && ra <= rb){ST[i] = L;} else {int m = (l + r) / 2;T ma = L.get(x[m]);T mb = ST[i].get(x[m]);if (ma < mb){swap(L, ST[i]);swap(la, lb);swap(ra, rb);}if (la < lb){line_add(L, i * 2 + 1, l, m);}if (ra < rb){line_add(L, i * 2 + 2, m, r);}}}void line_add(T a, T b){line_add(line(a, b), 0, 0, N);}T get(T x2){int p = lower_bound(x.begin(), x.end(), x2) - x.begin();p += N - 1;T ans = INF;ans = min(ans, ST[p].get(x2));while (p > 0){p = (p - 1) / 2;ans = min(ans, ST[p].get(x2));}return ans;}};int main(){vector<int> N(3);for (int i = 0; i < 3; i++){cin >> N[i];}vector<vector<int>> A(3);for (int i = 0; i < 3; i++){A[i].resize(N[i]);for (int j = 0; j < N[i]; j++){cin >> A[i][j];}}vector<vector<int>> B(3, vector<int>(MAX * 2 + 1, 0));for (int i = 0; i < 3; i++){for (int j = 0; j < N[i]; j++){B[i][A[i][j] + MAX]++;}}int M = MAX * 2 + 2;vector<vector<long long>> X(3, vector<long long>(M, 0));vector<vector<long long>> Y(3, vector<long long>(M, 0));for (int i = 0; i < 3; i++){for (int j = 0; j <= MAX * 2; j++){X[i][j + 1] = X[i][j] + B[i][MAX * 2 - j];Y[i][j + 1] = Y[i][j] + B[i][MAX * 2 - j] * (MAX - j);}}vector<int> p(M);for (int i = 0; i < M; i++){p[i] = i;}sort(p.begin(), p.end(), [&](int i, int j){return Y[1][i] < Y[1][j];});auto cross = [](pair<long long, long long> L1, pair<long long, long long> L2){if (L1.second - L2.second >= 0){return (L1.second - L2.second) / (L2.first - L1.first);} else {return (L1.second - L2.second - (L2.first - L1.first - 1)) / (L2.first - L1.first);}};long long ans = 0;for (int i = 0; i < M; i++){vector<pair<long long, long long>> L(M);for (int j = 0; j < M; j++){L[j] = make_pair(Y[1][p[j]], Y[0][i] * X[1][p[j]]);}vector<pair<long long, long long>> L2;L2.push_back(L[0]);for (int j = 1; j < M; j++){if (L[j].first == L2.back().first){if (L[j].second > L2.back().second){L2.back() = L[j];}} else {while (L2.size() >= 2){pair<long long, long long> c1 = L2[L2.size() - 2];pair<long long, long long> c2 = L2[L2.size() - 1];pair<long long, long long> c3 = L[j];if (cross(c1, c2) > cross(c2, c3)){L2.pop_back();} else {break;}}L2.push_back(L[j]);}}int cnt = L2.size();int idx = 0;for (int j = 0; j < M; j++){while (idx < cnt - 1){long long x = L2[idx].first * X[2][j] + L2[idx].second;long long y = L2[idx + 1].first * X[2][j] + L2[idx + 1].second;if (x < y){idx++;} else {break;}}ans = max(ans, L2[idx].first * X[2][j] + L2[idx].second + Y[2][j] * X[0][i]);}}cout << ans << endl;}