#490111 (C++17) No.1309 テスト

提出ソース

結果

問題	No.1309 テスト
ユーザー	beet
提出日時	2020-05-31 21:31:38
言語	C++17 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	313 ms / 4,000 ms
コード長	6,783 bytes
コンパイル時間	2,464 ms
コンパイル使用メモリ	203,556 KB
実行使用メモリ	4,380 KB
最終ジャッジ日時	2023-10-11 04:04:08
合計ジャッジ時間	7,129 ms
ジャッジサーバーID （参考情報）	judge14 / judge13

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	98 ms 4,372 KB
testcase_01	AC	2 ms 4,376 KB
testcase_02	AC	2 ms 4,372 KB
testcase_03	AC	2 ms 4,376 KB
testcase_04	AC	1 ms 4,372 KB
testcase_05	AC	2 ms 4,372 KB
testcase_06	AC	2 ms 4,372 KB
testcase_07	AC	2 ms 4,372 KB
testcase_08	AC	2 ms 4,376 KB
testcase_09	AC	2 ms 4,376 KB
testcase_10	AC	1 ms 4,372 KB
testcase_11	AC	2 ms 4,372 KB
testcase_12	AC	2 ms 4,372 KB
testcase_13	AC	1 ms 4,376 KB
testcase_14	AC	2 ms 4,376 KB
testcase_15	AC	2 ms 4,376 KB
testcase_16	AC	2 ms 4,372 KB
testcase_17	AC	1 ms 4,372 KB
testcase_18	AC	2 ms 4,376 KB
testcase_19	AC	2 ms 4,376 KB
testcase_20	AC	1 ms 4,380 KB
testcase_21	AC	2 ms 4,372 KB
testcase_22	AC	2 ms 4,376 KB
testcase_23	AC	2 ms 4,376 KB
testcase_24	AC	1 ms 4,376 KB
testcase_25	AC	2 ms 4,376 KB
testcase_26	AC	2 ms 4,372 KB
testcase_27	AC	1 ms 4,372 KB
testcase_28	AC	2 ms 4,372 KB
testcase_29	AC	2 ms 4,376 KB
testcase_30	AC	2 ms 4,376 KB
testcase_31	AC	1 ms 4,372 KB
testcase_32	AC	2 ms 4,372 KB
testcase_33	AC	1 ms 4,372 KB
testcase_34	AC	1 ms 4,376 KB
testcase_35	AC	1 ms 4,376 KB
testcase_36	AC	1 ms 4,372 KB
testcase_37	AC	2 ms 4,372 KB
testcase_38	AC	1 ms 4,372 KB
testcase_39	AC	1 ms 4,376 KB
testcase_40	AC	1 ms 4,376 KB
testcase_41	AC	2 ms 4,372 KB
testcase_42	AC	2 ms 4,376 KB
testcase_43	AC	1 ms 4,376 KB
testcase_44	AC	1 ms 4,376 KB
testcase_45	AC	2 ms 4,372 KB
testcase_46	AC	2 ms 4,372 KB
testcase_47	AC	2 ms 4,372 KB
testcase_48	AC	3 ms 4,372 KB
testcase_49	AC	3 ms 4,376 KB
testcase_50	AC	2 ms 4,372 KB
testcase_51	AC	3 ms 4,372 KB
testcase_52	AC	2 ms 4,372 KB
testcase_53	AC	3 ms 4,376 KB
testcase_54	AC	3 ms 4,372 KB
testcase_55	AC	3 ms 4,372 KB
testcase_56	AC	2 ms 4,372 KB
testcase_57	AC	2 ms 4,376 KB
testcase_58	AC	3 ms 4,372 KB
testcase_59	AC	2 ms 4,372 KB
testcase_60	AC	2 ms 4,376 KB
testcase_61	AC	2 ms 4,376 KB
testcase_62	AC	2 ms 4,376 KB
testcase_63	AC	2 ms 4,372 KB
testcase_64	AC	2 ms 4,376 KB
testcase_65	AC	57 ms 4,372 KB
testcase_66	AC	122 ms 4,376 KB
testcase_67	AC	84 ms 4,372 KB
testcase_68	AC	77 ms 4,372 KB
testcase_69	AC	107 ms 4,376 KB
testcase_70	AC	114 ms 4,372 KB
testcase_71	AC	283 ms 4,376 KB
testcase_72	AC	313 ms 4,372 KB
testcase_73	AC	304 ms 4,372 KB
testcase_74	AC	22 ms 4,372 KB
testcase_75	AC	11 ms 4,372 KB
testcase_76	AC	13 ms 4,376 KB
testcase_77	AC	7 ms 4,372 KB
testcase_78	AC	2 ms 4,376 KB
testcase_79	AC	1 ms 4,372 KB
testcase_80	AC	1 ms 4,372 KB
testcase_81	AC	2 ms 4,376 KB
testcase_82	AC	1 ms 4,376 KB
testcase_83	AC	2 ms 4,372 KB
testcase_84	AC	196 ms 4,380 KB
testcase_85	AC	107 ms 4,372 KB
testcase_86	AC	65 ms 4,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
}

yukicoder

結果

テストケース

ソースコード