結果
問題 | No.1309 テスト |
ユーザー | beet |
提出日時 | 2020-05-31 21:31:38 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 300 ms / 4,000 ms |
コード長 | 6,783 bytes |
コンパイル時間 | 2,071 ms |
コンパイル使用メモリ | 197,076 KB |
最終ジャッジ日時 | 2025-01-10 20:11:25 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 85 |
ソースコード
#include <bits/stdc++.h> using namespace std; template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;} using Int = long long; const char newl = '\n'; //INSERT ABOVE HERE // |{ x | x \in [s, t]}| Int num(Int s,Int t){ assert(s<=t+1); return t-s+1; } // take n min elements from [s, t] Int calc_lb(Int s,Int t,Int n){ assert(num(s,t)>=n); return (s+s+n-1)*n/2; } // take n max elements from [s, t] Int calc_ub(Int s,Int t,Int n){ assert(num(s,t)>=n); return (t-(n-1)+t)*n/2; } // sum of [s, t] Int calc(Int s,Int t){ assert(s<=t+1); return (s+t)*(t-s+1)/2; } Int N,P,X,Y; // take X * F if S_contains_X // take C1 from [S1, T1] * F // take U from [S1, T1] at most F-1 // take C2 from [S2, T2] * F Int type01(Int F,Int C,Int S_contains_X, Int S1,Int T1,Int C1,Int U1, Int S2,Int T2,Int C2,Int U2){ assert(C1 + S_contains_X + C2 == C); assert(U1 > 0 and U2==0); Int D1=(U1-1)/(F-1); Int E1=U1-D1*(F-1); assert(0<=D1 and 0<E1 and E1<=(F-1)); assert(num(S1,T1)>=C1+D1+1); assert(num(S2,T2)>=C2); Int act_X = X * S_contains_X; const Int INF = 1e18; Int res=-INF; { Int lb=calc_lb(S1,T1-(D1+1),C1)+act_X+calc_lb(S2,T2,C2); Int ub=calc_ub(S1,T1-(D1+1),C1)+act_X+calc_ub(S2,T2,C2); if(lb<=Y*C and Y*C<=ub) chmax(res, +Y*C*F +(T1-D1)*E1 +calc(T1-D1+1,T1)*(F-1)); } { Int lb=calc_lb(T1-(C1+D1)+1,T1,C1)+act_X+calc(T2-C2+1,T2); Int ub=calc_ub(T1-(C1+D1)+1,T1,C1)+act_X+calc(T2-C2+1,T2); if(lb<=Y*C and Y*C<=ub) chmax(res, +Y*C +(calc(T1-(C1+D1)+1,T1)+act_X+calc(T2-C2+1,T2))*(F-1) +(T1-(C1+D1))*E1); } { Int diff=(+calc(T1-(C1+D1)+1,T1-D1) +act_X +calc(T2-C2+1,T2))-Y*C; //cout<<F<<' '<<C1<<' '<<S_contains_X<<' '<<C2<<':'<<diff<<endl; if(0<=diff and diff<=C1) chmax(res, +Y*C*F +(T1-(C1+D1)+diff)*E1 +calc(T1-D1+1,T1)*(F-1)); } return res; } // take X * F if S_contains_X // take C1 from [S1, T1] * F // take U1 from [S1, T1] at most F-1 // take C2 from [S2, T2] * F // take U2 from [S2, T2] at most F-1 Int type02(Int F,Int C,Int S_contains_X, Int S1,Int T1,Int C1,Int U1, Int S2,Int T2,Int C2,Int U2){ assert(C1 + S_contains_X + C2 == C); assert(U1 > 0 and U2 > 0); Int D1=(U1-1)/(F-1); Int E1=U1-D1*(F-1); assert(0<=D1 and 0<E1 and E1<=(F-1)); Int D2=(U2-1)/(F-1); Int E2=U2-D2*(F-1); assert(0<=D2 and 0<E2 and E2<=(F-1)); assert(num(S1,T1)>=C1+D1+1); assert(num(S2,T2)>=C2+D2+1); Int act_X = X * S_contains_X; const Int INF = 1e18; Int res=-INF; { Int lb=calc_lb(S1,T1-(D1+1),C1)+act_X+calc_lb(S2,T2-(D2+1),C2); Int ub=calc_ub(S1,T1-(D1+1),C1)+act_X+calc_ub(S2,T2-(D2+1),C2); if(lb<=Y*C and Y*C<=ub) chmax(res, +Y*C*F +(T1-D1)*E1 +calc(T1-D1+1,T1)*(F-1) +(T2-D2)*E2 +calc(T2-D2+1,T2)*(F-1)); } { Int lb=calc_lb(T1-(C1+D1)+1,T1,C1)+act_X+calc_lb(T2-(C2+D2)+1,T2,C2); Int ub=calc_ub(T1-(C1+D1)+1,T1,C1)+act_X+calc_ub(T2-(C2+D2)+1,T2,C2); if(lb<=Y*C and Y*C<=ub) chmax(res, +Y*C +(calc(T1-(C1+D1)+1,T1)+act_X+calc(T2-(C2+D2)+1,T2))*(F-1) +(T1-(C1+D1))*E1 +(T2-(C2+D2))*E2); } { Int diff=(+calc(T1-(C1+D1)+1,T1-D1) +act_X +calc(T2-(C2+D2+1)+1,T2-(D2+1)))-Y*C; if(0<=diff and diff<=C1) chmax(res, +Y*C*F +(T1-(C1+D1)+diff)*E1 +calc(T1-D1+1,T1)*(F-1) +(T2-D2)*E2 +calc(T2-D2+1,T2)*(F-1)); } { Int diff=(+calc(T1-(C1+D1)+1,T1-D1) +act_X +calc(T2-(C2+D2)+1,T2-D2))-Y*C; if(0<=diff and diff<=C2) chmax(res, +Y*C*F +(T1-(C1+D1))*E1 +calc(T1-D1+1,T1)*(F-1) +(T2-(C2+D2)+diff)*E2 +calc(T2-D2+1,T2)*(F-1)); } return res; } signed solve(){ cin>>N>>P>>X>>Y; assert(N&1); if(N==1){ if(X==Y) cout<<X<<newl; else cout<<-1<<newl; return 0; } if(X==0){ if(X==Y) cout<<P*(N/2)<<newl; else cout<<-1<<newl; return 0; } if(X==P){ if(X==Y) cout<<P*N<<newl; else cout<<-1<<newl; return 0; } Int ans=-1; /* S: set of mode F: frequency of mode C: |S| (\sum_{s \in S} s) = Y * C */ // F = 1 -> sum = Y * N // X \in S if(num(0,X-1)>=N/2 and num(X+1,P)>=N/2){ Int sum=Y*N; Int lb=calc_lb(0,X-1,N/2)+X+calc_lb(X+1,P,N/2); Int ub=calc_ub(0,X-1,N/2)+X+calc_ub(X+1,P,N/2); if(lb<=sum and sum<=ub) chmax(ans,sum); } // F > 1 for(Int F=2;F<=N;F++){ for(Int C=1;C*F<=N;C++){ for(Int S_contains_X=0;S_contains_X<=1;S_contains_X++){ for(Int A=0;A+S_contains_X<=C;A++){ Int B=C-A-S_contains_X; if(!(num(0,X-1)>=A and num(X+1,P)>=B)) continue; Int act_X = X * S_contains_X; { Int lb=calc_lb(0,X-1,A)+act_X+calc_lb(X+1,P,B); Int ub=calc_ub(0,X-1,A)+act_X+calc_ub(X+1,P,B); if(!(lb<=Y*C and Y*C<=ub)) continue; } //cout<<F<<':'<<A<<' '<<S_contains_X<<' '<<B<<endl; Int V=min({(num(X+1,P)-B)*(F-1),N/2-B*F,N-C*F}); Int W=S_contains_X?0:min(N-C*F-V,F-1); Int U=N-C*F-V-W; //cout<<':'<<U<<' '<<V<<' '<<W<<endl; if(!(U>=0 and V>=0)) continue; if(!S_contains_X and !(W>0)) continue; if(!(num(0,X-1)>=A+(U+(F-2))/(F-1))) continue; if(!(num(X+1,P)>=B+(V+(F-2))/(F-1))) continue; if(!(A*F+U<=N/2 and B*F+V<=N/2)) continue; //cout<<A<<' '<<S_contains_X<<' '<<B<<endl; if(U==0 and V==0){ chmax(ans,Y*C*F+W*X); continue; } if(V==0){ chmax(ans, type01(F,C,S_contains_X, 0,X-1,A,U, X+1,P,B,V)+W*X); continue; } if(U==0){ chmax(ans, type01(F,C,S_contains_X, X+1,P,B,V, 0,X-1,A,U)+W*X); continue; } chmax(ans, type02(F,C,S_contains_X, 0,X-1,A,U, X+1,P,B,V)+W*X); chmax(ans, type02(F,C,S_contains_X, X+1,P,B,V, 0,X-1,A,U)+W*X); } } } } cout<<ans<<newl; return 0; } signed main(){ cin.tie(0); ios::sync_with_stdio(0); const Int T = 10; for(Int t=0;t<T;t++) solve(); return 0; }