#937609 (C++17) No.2581 [Cherry Anniversary 3] 28輪の桜のブーケ

• 問題: No.2581 [Cherry Anniversary 3] 28輪の桜のブーケ
• ユーザー: umezo
• 提出日時: 2023-12-09 02:12:17
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 155 ms / 3,000 ms
• コード長: 1,095 bytes
• コンパイル時間: 2,123 ms
• コンパイル使用メモリ: 207,440 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-09-27 03:27:05
• 合計ジャッジ時間: 4,740 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	8 ms; 5,248 KB
testcase_01	AC	9 ms; 5,376 KB
testcase_02	AC	13 ms; 5,376 KB
testcase_03	AC	49 ms; 5,376 KB
testcase_04	AC	31 ms; 5,376 KB
testcase_05	AC	10 ms; 5,376 KB
testcase_06	AC	40 ms; 5,376 KB
testcase_07	AC	42 ms; 5,376 KB
testcase_08	AC	15 ms; 5,376 KB
testcase_09	AC	28 ms; 5,376 KB
testcase_10	AC	41 ms; 5,376 KB
testcase_11	AC	14 ms; 5,376 KB
testcase_12	AC	52 ms; 5,376 KB
testcase_13	AC	60 ms; 5,376 KB
testcase_14	AC	52 ms; 5,376 KB
testcase_15	AC	48 ms; 5,376 KB
testcase_16	AC	49 ms; 5,376 KB
testcase_17	AC	47 ms; 5,376 KB
testcase_18	AC	53 ms; 5,376 KB
testcase_19	AC	59 ms; 5,376 KB
testcase_20	AC	59 ms; 5,376 KB
testcase_21	AC	57 ms; 5,376 KB
testcase_22	AC	144 ms; 5,376 KB
testcase_23	AC	155 ms; 5,376 KB
testcase_24	AC	151 ms; 5,376 KB
testcase_25	AC	142 ms; 5,376 KB
testcase_26	AC	148 ms; 5,376 KB
testcase_27	AC	10 ms; 5,376 KB
testcase_28	AC	9 ms; 5,376 KB
testcase_29	AC	118 ms; 5,376 KB
testcase_30	AC	22 ms; 5,376 KB
testcase_31	AC	52 ms; 5,376 KB

ソースコード

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(v) v.begin(),v.end()
typedef long long ll;
 
#include<bits/stdc++.h>
using namespace std;
 
vector<ll> A[15],B[15];
ll G[28],H[28];
 
int main(){
  int m;
  cin>>m;
  rep(i,28) cin>>G[i];
  rep(i,28) cin>>H[i];
  
  rep(bit,1<<14){
    int a=__builtin_popcount(bit);
    ll sum=0,sum1=0;
    rep(i,14){
      if(bit&(1<<i)){
        sum=(sum+G[i])%m;
        sum1=(sum1+G[i+14])%m;
      }
      else{
        sum=(sum+H[i])%m;
        sum1=(sum1+H[i+14])%m;
      }
    }
    A[a].push_back(sum);
    B[a].push_back(sum1);
  }
  rep(i,15) sort(ALL(A[i])),sort(ALL(B[i]));
  
  int q;
  cin>>q;
  rep(_,q){
    int k,x;
    cin>>k>>x;
    int ans=0;
    for(int a=0;a<=14;a++){
      if(k-a<0 || k-a>14) continue;
      for(auto p:A[a]){
        int q=0,r=0;;
        if(x>=p) q=upper_bound(ALL(B[k-a]),m-p-1)-lower_bound(ALL(B[k-a]),x-p);
        else{
          q=upper_bound(ALL(B[k-a]),m-p-1)-B[k-a].begin();
          r=B[k-a].end()-lower_bound(ALL(B[k-a]),m-p+x);
        }
        ans+=q+r;
      }
    }
    cout<<ans<<endl;
  }
}