結果

問題 No.2495 Three Sets
ユーザー ococonomy1ococonomy1
提出日時 2023-10-06 22:27:54
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 55 ms / 3,000 ms
コード長 3,193 bytes
コンパイル時間 1,562 ms
コンパイル使用メモリ 122,940 KB
実行使用メモリ 7,864 KB
最終ジャッジ日時 2023-10-06 22:27:57
合計ジャッジ時間 3,098 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 2 ms
4,380 KB
testcase_11 AC 2 ms
4,376 KB
testcase_12 AC 2 ms
4,376 KB
testcase_13 AC 21 ms
4,868 KB
testcase_14 AC 40 ms
6,124 KB
testcase_15 AC 26 ms
5,164 KB
testcase_16 AC 55 ms
7,864 KB
testcase_17 AC 55 ms
7,772 KB
testcase_18 AC 2 ms
4,380 KB
testcase_19 AC 36 ms
7,864 KB
testcase_20 AC 33 ms
7,724 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <complex>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>
using namespace std;
using lg = long long;
using pii = pair<int, int>;
using pll = pair<lg, lg>;
#define TEST cerr << "TEST" << endl
#define AMARI 998244353
// #define AMARI 1000000007
#define TEMOTO ((sizeof(long double) == 16) ? false : true)
#define TIME_LIMIT 1980 * (TEMOTO ? 1 : 1000)
#define el '\n'
#define El '\n'

int na,nb,nc;
vector<lg> a,b,c;
vector<lg> ar,br,cr;

//0:1個も選ばない na:全部選ぶ
lg calcxyz(int x,int y,int z){
    //この時、全部定まってるから具体的に出せる
    lg ans = ar[x] * (lg)y + br[y] * (lg)z + cr[z] * (lg)x;
    return ans;
}

//xとyを固定した時の最大値
lg calcxy(int x,int y){
    int lz = 0,rz = nc;
    while(rz - lz >= 3){
        int cz1 = ((2 * lz) + rz) / 3;
        int cz2 = (lz + (2 * rz)) / 3;
        if(cz1 == cz2)break;
        if(calcxyz(x,y,cz1) > calcxyz(x,y,cz2))rz = cz2;
        else lz = cz1;
    }
    lg ans = 0;
    for(int i = lz; i <= rz; i++){
        ans = max(ans,calcxyz(x,y,i));
    }
    return ans;
}

//xを固定した時の最大値
map<int,lg> mp;
lg calcx(int x){
    if(mp.find(x) != mp.end()){
        return mp[x];
    }
    int ly = 0,ry = nb;
    while(ry - ly >= 3){
        int cy1 = ((2 * ly) + ry) / 3;
        int cy2 = (ly + (2 * ry)) / 3;
        if(cy1 == cy2)break;
        if(calcxy(x,cy1) > calcxy(x,cy2))ry = cy2;
        else ly = cy1;
    }
    lg ans = 0;
    for(int i = ly; i <= ry; i++){
        ans = max(ans,calcxy(x,i));
    }
    return mp[x] = ans;
}

#define MULTI_TEST_CASE false
void solve(void) {
    cin >> na >> nb >> nc;
    a.resize(na); b.resize(nb); c.resize(nc);
    ar.resize(na + 1); br.resize(nb + 1); cr.resize(nc + 1);
    for(int i = 0; i < na; i++)cin >> a[i];
    for(int i = 0; i < nb; i++)cin >> b[i];
    for(int i = 0; i < nc; i++)cin >> c[i];
    sort(a.rbegin(),a.rend());
    sort(b.rbegin(),b.rend());
    sort(c.rbegin(),c.rend());
    ar[0] = br[0] = cr[0] = 0;
    for(int i = 0; i < na; i++){
        ar[i + 1] = ar[i] + a[i];
    }
    for(int i = 0; i < nb; i++){
        br[i + 1] = br[i] + b[i];
    }
    for(int i = 0; i < nc; i++){
        cr[i + 1] = cr[i] + c[i];
    }
    lg ans = 0;
    //aについて[0,x]から選ぶ,ということを考える時の添え字が[lx,rx]
    int lx = 0,rx = na;
    while(rx - lx >= 3){
        int cx1 = ((2 * lx) + rx) / 3;
        int cx2 = (lx + (2 * rx)) / 3;
        if(cx1 == cx2)break;
        if(calcx(cx1) > calcx(cx2))rx = cx2;
        else lx = cx1;
    }
    for(int i = lx; i <= rx; i++){
        ans = max(ans,calcx(i));
    }
    cout << ans << el;
    return;
}

void calc(void) {
    return;
}

int main(void) {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    calc();
    int t = 1;
    if(MULTI_TEST_CASE) cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}
0