#1194261 (C++17) No.2495 Three Sets

• 問題: No.2495 Three Sets
• ユーザー: GOTKAKO
• 提出日時: 2026-10-23 07:05:28
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 117 ms / 3,000 ms
• コード長: 3,113 bytes
• コンパイル時間: 1,380 ms
• コンパイル使用メモリ: 220,152 KB
• 実行使用メモリ: 9,920 KB
• 最終ジャッジ日時: 2026-10-23 07:05:35
• 合計ジャッジ時間: 7,136 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

ファイルパターン	結果
sample	AC * 3
other	AC * 22

ソースコード

#include <bits/stdc++.h>
using namespace std;


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int Na,Nb,Nc; cin >> Na >> Nb >> Nc;
    if(false){   
        vector<int> A(Na),B(Nb),C(Nc);
        for(auto &a : A) cin >> a;
        for(auto &b : B) cin >> b;
        for(auto &c : C) cin >> c;

        int ca = 0,sa = 0,cb = 0,sb = 0,cc = 0,sc = 0,answer = 0;
        vector<int> X,Y,Z;
        auto dfs = [&](auto dfs,int pos) -> void {
            if(pos == Na+Nb+Nc){

                answer = max(answer,sa*cb+sb*cc+sc*ca);
                if(answer == 45000){
                    for(auto x : X) cout << x << " "; cout << endl;
                    for(auto x : Y) cout << x << " "; cout << endl;
                    for(auto x : Z) cout << x << " "; cout << endl;
                    exit(0);
                }
                return;
            }
            else if(pos < Na){
                dfs(dfs,pos+1);
                sa += A.at(pos),ca++,X.push_back(A.at(pos));
                dfs(dfs,pos+1);
                sa -= A.at(pos),ca--,X.pop_back();
            }
            else if(pos < Na+Nb){
                dfs(dfs,pos+1);
                sb += B.at(pos-Na),cb++,Y.push_back(B.at(pos-Na));
                dfs(dfs,pos+1);
                sb -= B.at(pos-Na),cb--,Y.pop_back();
            }
            else{
                dfs(dfs,pos+1);
                sc += C.at(pos-Na-Nb),cc++,Z.push_back(C.at(pos-Na-Nb));
                dfs(dfs,pos+1);
                sc -= C.at(pos-Na-Nb),cc--,Z.pop_back();
            }
        };
        dfs(dfs,0);
        cout << answer << endl;
    }
    
    vector<long long> suma(6009),sumb(6009),sumc(6009),Va(6009),Vb(6009),Vc(6009);
    for(int i=0; i<Na; i++){
        int a; cin >> a;
        suma.at(a+3000) += a;
        Va.at(a+3000)++; 
    }
    for(int i=0; i<Nb; i++){
        int b; cin >> b;
        sumb.at(b+3000) += b;
        Vb.at(b+3000)++;
    }
    for(int i=0; i<Nc; i++){
        int c; cin >> c; 
        sumc.at(c+3000) += c;
        Vc.at(c+3000)++;
    }

    for(int i=6007; i>=0; i--) Va.at(i) += Va.at(i+1);
    for(int i=6007; i>=0; i--) Vb.at(i) += Vb.at(i+1);
    for(int i=6007; i>=0; i--) Vc.at(i) += Vc.at(i+1);
    for(int i=6007; i>=0; i--) suma.at(i) += suma.at(i+1);
    for(int i=6007; i>=0; i--) sumb.at(i) += sumb.at(i+1);
    for(int i=6007; i>=0; i--) sumc.at(i) += sumc.at(i+1);


    long long answer = 0;
    for(int i=0; i<=6001; i++){
        long long sa = suma.at(i), va = Va.at(i);
        for(int k=0; k<=6001; k++){
            long long sb = sumb.at(k),vb = Vb.at(k);
            long long now = sa*vb;
            if(va == 0){
                answer = max({answer,now,now+sb*Nc});
                continue;
            }

            long long border = (-sb+va-1)/va;
            if(sb > 0) border = -sb/va;
            if(border > 3000) border = 3001;
            if(border < -3000) border = -3000; 
            long long sc = sumc.at(border+3000),vc = Vc.at(border+3000);
            answer = max(answer,now+sc*va+sb*vc);
        }
    }
    cout << answer << endl;
}