結果
問題 | No.2495 Three Sets |
ユーザー | 沙耶花 |
提出日時 | 2023-10-06 22:27:45 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,410 ms / 3,000 ms |
コード長 | 1,485 bytes |
コンパイル時間 | 5,508 ms |
コンパイル使用メモリ | 267,436 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-26 16:37:09 |
合計ジャッジ時間 | 12,519 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 |
ソースコード
#include <stdio.h> #include <atcoder/all> #include <bits/stdc++.h> using namespace std; using namespace atcoder; using mint = modint998244353; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000001 #define Inf64 1000000000000000001 long long A,B,C; vector<long long> a,b,c; long long get2(long long x,long long y,long long mid){ return x * c[mid] + y * mid; } long long get(long long x,long long y,long long mid){ long long l = 0,r = C; while(r-l>=3){ long long m0 = l + (r-l)/3; long long m1 = m0 + (r-l)/3; if(get2(x,b[mid],m0) <= get2(x,b[mid],m1))l = m0; else r = m1; } long long ret = -Inf64; for(long long i=max(0LL,l-2);i<=min(C,r+2);i++)ret = max(ret,get2(x,b[mid],i)); return ret + y * mid; } int main(){ cin>>A>>B>>C; a.resize(A),b.resize(B),c.resize(C); //vector<long long> a(A),b(B),c(C); rep(i,a.size())cin>>a[i]; rep(i,b.size())cin>>b[i]; rep(i,c.size())cin>>c[i]; sort(a.rbegin(),a.rend()); sort(b.rbegin(),b.rend()); sort(c.rbegin(),c.rend()); b.insert(b.begin(),0); c.insert(c.begin(),0); rep(i,B)b[i+1] += b[i]; rep(i,C)c[i+1] += c[i]; long long x = 0,y = 0; long long ans = -Inf64; rep(i,A+1){ x = i; long long l = 0,r = B; while(r-l>=3){ long long m0 = l + (r-l)/3; long long m1 = m0 + (r-l)/3; if(get(x,y,m0) <= get(x,y,m1))l = m0; else r = m1; } for(long long i=max(0LL,l-2);i<=min(B,r+2);i++)ans = max(ans,get(x,y,i)); if(i<A)y += a[i]; } cout<<ans<<endl; return 0; }