結果

問題 No.1309 テスト
ユーザー beetbeet
提出日時 2020-05-31 18:31:39
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 6,782 bytes
コンパイル時間 2,397 ms
コンパイル使用メモリ 206,008 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-13 03:25:14
合計ジャッジ時間 5,939 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 70 ms
5,248 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 WA -
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 WA -
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 2 ms
5,376 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 2 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 2 ms
5,376 KB
testcase_22 AC 2 ms
5,376 KB
testcase_23 AC 2 ms
5,376 KB
testcase_24 AC 2 ms
5,376 KB
testcase_25 WA -
testcase_26 AC 2 ms
5,376 KB
testcase_27 WA -
testcase_28 AC 2 ms
5,376 KB
testcase_29 AC 2 ms
5,376 KB
testcase_30 AC 2 ms
5,376 KB
testcase_31 AC 2 ms
5,376 KB
testcase_32 AC 2 ms
5,376 KB
testcase_33 AC 2 ms
5,376 KB
testcase_34 WA -
testcase_35 AC 2 ms
5,376 KB
testcase_36 AC 2 ms
5,376 KB
testcase_37 AC 2 ms
5,376 KB
testcase_38 WA -
testcase_39 WA -
testcase_40 AC 2 ms
5,376 KB
testcase_41 WA -
testcase_42 AC 2 ms
5,376 KB
testcase_43 WA -
testcase_44 AC 2 ms
5,376 KB
testcase_45 AC 2 ms
5,376 KB
testcase_46 WA -
testcase_47 AC 2 ms
5,376 KB
testcase_48 WA -
testcase_49 AC 2 ms
5,376 KB
testcase_50 WA -
testcase_51 WA -
testcase_52 WA -
testcase_53 WA -
testcase_54 AC 2 ms
5,376 KB
testcase_55 WA -
testcase_56 AC 2 ms
5,376 KB
testcase_57 AC 2 ms
5,376 KB
testcase_58 WA -
testcase_59 WA -
testcase_60 AC 2 ms
6,940 KB
testcase_61 WA -
testcase_62 AC 2 ms
6,940 KB
testcase_63 WA -
testcase_64 WA -
testcase_65 AC 41 ms
6,940 KB
testcase_66 AC 87 ms
6,944 KB
testcase_67 AC 60 ms
6,940 KB
testcase_68 AC 56 ms
6,940 KB
testcase_69 AC 77 ms
6,944 KB
testcase_70 AC 83 ms
6,940 KB
testcase_71 AC 206 ms
6,940 KB
testcase_72 AC 222 ms
6,940 KB
testcase_73 AC 215 ms
6,944 KB
testcase_74 WA -
testcase_75 WA -
testcase_76 WA -
testcase_77 WA -
testcase_78 AC 2 ms
6,944 KB
testcase_79 AC 1 ms
6,944 KB
testcase_80 AC 2 ms
6,940 KB
testcase_81 AC 2 ms
6,940 KB
testcase_82 AC 2 ms
6,944 KB
testcase_83 AC 2 ms
6,944 KB
testcase_84 AC 139 ms
6,944 KB
testcase_85 AC 78 ms
6,940 KB
testcase_86 AC 47 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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 use_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 use_X,
           Int S1,Int T1,Int C1,Int U,
           Int S2,Int T2,Int C2){

  Int D=(U-1)/(F-1);
  Int E=U-D*(F-1);
  assert(0<=D and 0<E and E<=(F-1));

  assert(num(S1,T1)>=C1+D+1);
  assert(num(S2,T2)>=C2);

  {
    Int lb=calc_lb(S1,T1-(D+1),C1)+X*use_X+calc_lb(S2,T2,C2);
    Int ub=calc_ub(S1,T1-(D+1),C1)+X*use_X+calc_ub(S2,T2,C2);
    if(lb<=Y*C and Y*C<=ub){
      return
        +Y*C*F
        +(T1-D)*E
        +calc(T1-D+1,T1)*(F-1);
    }
  }
  {
    Int lb=calc_lb(T1-(C1+D)+1,T1,C1)+X*use_X+calc(T2-C2+1,T2);
    Int ub=calc_ub(T1-(C1+D)+1,T1,C1)+X*use_X+calc(T2-C2+1,T2);
    if(lb<=Y*C and Y*C<=ub){
      return
        +Y*C
        +(calc(T1-(C1+D)+1,T1)+X*use_X)*(F-1)
        +(T1-(C1+D))*E
        +calc(T2-C2+1,T2)*(F-1);
    }
  }

  Int diff=(calc(T1-(C1+D)+1,T1-D)+X*use_X+calc(T2-C2+1,T2))-Y*C;
  assert(0<diff and diff<C1);
  return
           +Y*C*F
           +(T1-(C1+D)+diff)*E
           +calc(T2-C2+1,T2)*(F-1);
}


// take X * F if use_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 use_X,
           Int S1,Int T1,Int C1,Int U1,
           Int S2,Int T2,Int C2,Int U2){

  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 lb=calc_lb(S1,T1-(D1+1),C1)+X*use_X+calc_lb(S2,T2-(D2+1),C2);
    Int ub=calc_ub(S1,T1-(D1+1),C1)+X*use_X+calc_ub(S2,T2-(D2+1),C2);
    if(lb<=Y*C and Y*C<=ub){
      return
        +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)+X*use_X+calc_lb(T2-(C2+D2)+1,T2,C2);
    Int ub=calc_ub(T1-(C1+D1)+1,T1,C1)+X*use_X+calc_ub(T2-(C2+D2)+1,T2,C2);
    if(lb<=Y*C and Y*C<=ub){
      return
        +Y*C
        +(calc(T1-(C1+D1)+1,T1)+X*use_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)+X*use_X+calc(T2-(C2+D2+1)+1,T2-(D2+1)))-Y*C;
    if(0<=diff and diff<=C1)
      return
        +Y*C*F
        +(T1-(C1+D1)+diff)*E1
        +calc(T1-D1+1,T1)*(F-1)
        +(T2-C2)*E2
        +calc(T2-D2+1,T2)*(F-1);
  }

  Int diff=(calc(T1-(C1+D1)+1,T1-D1)+X*use_X+calc(T2-(C2+D2)+1,T2-(D2)))-Y*C;
  assert(0<=diff and diff<=C2);

  return
    +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);
}

signed solve(){
  cin>>N>>P>>X>>Y;

  if(N==1){
    if(X==Y) cout<<X<<newl;
    else cout<<-1<<newl;
    return 0;
  }

  if(X==0 or X==P){
    if(X==Y) cout<<X<<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++){
      // X \in S
      for(Int A=0;A<C;A++){
        Int B=C-A-1;
        //    (A)  (1)   (B)
        // [0, X-1] X [X+1, P]
        if(!(num(0,X-1)>=A and num(X+1,P)>=B)) continue;

        {
          Int lb=calc_lb(0,X-1,A)+X+calc_lb(X+1,P,B);
          Int ub=calc_ub(0,X-1,A)+X+calc_ub(X+1,P,B);
          if(!(lb<=Y*C and Y*C<=ub)) continue;
        }

        Int V=min((num(X+1,P)-B)*(F-1),N/2-B*F);
        Int U=N-C*F-V;
        if(!(U>=0 and V>=0)) continue;
        if(!(num(0,X-1)>=A+(U+(F-2))/(F-1))) continue;

        if(U==0 and V==0){
          chmax(ans,Y*C*F);
          continue;
        }

        if(V==0){
          chmax(ans,
                type01(F,C,1,
                       0,X-1,A,U,
                       X+1,P,B));
          continue;
        }

        if(U==0){
          chmax(ans,
                type01(F,C,1,
                       X+1,P,B,V,
                       0,X-1,A));
          continue;
        }

        chmax(ans,
              type02(F,C,1,
                     0,X-1,A,U,
                     X+1,P,B,V));
        chmax(ans,
              type02(F,C,1,
                     X+1,P,B,V,
                     0,X-1,A,U));
      }

      // X \not\in S
      if(!(C*F<N)) continue;

      for(Int A=0;A<=C;A++){
        Int B=C-A;
        //    (A)  (0)   (B)
        // [0, X-1] X [X+1, P]
        if(!(num(0,X-1)>=A and num(X+1,P)>=B)) continue;

        {
          Int lb=calc_lb(0,X-1,A)+calc_lb(X+1,P,B);
          Int ub=calc_ub(0,X-1,A)+calc_ub(X+1,P,B);
          if(!(lb<=Y*C and Y*C<=ub)) continue;
        }

        Int V=min((num(X+1,P)-B)*(F-1),N/2-B*F);
        Int W=min(N-C*F-V,F-1);
        Int U=N-C*F-V-W;
        if(!(U>=0 and V>=0 and W>0)) continue;
        if(!(num(0,X-1)>=A+(U+(F-2))/(F-1))) continue;
        if(!(A*F+U<=N/2 and B*F+V<=N/2)) continue;

        if(U==0 and V==0){
          chmax(ans,Y*C*F+W*X);
          continue;
        }

        if(V==0){
          chmax(ans,
                type01(F,C,0,
                       0,X-1,A,U,
                       X+1,P,B)+W*X);
          continue;
        }

        if(U==0){
          chmax(ans,
                type01(F,C,0,
                       X+1,P,B,V,
                       0,X-1,A)+W*X);
          continue;
        }

        chmax(ans,
              type02(F,C,0,
                     0,X-1,A,U,
                     X+1,P,B,V)+W*X);
        chmax(ans,
              type02(F,C,0,
                     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;
}
0