fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,q,x,y;
  4. int ***dp;
  5. queue<pair<int,pair<int,int>>>qu;
  6. int cnt[667][3];
  7. pair<int,int>tv[100001];
  8. bool vis[667];
  9. void process(){
  10.     int imn,ipl,jmn,jpl,kmn,kpl;
  11.     int ii,jj,kk;
  12.     while(qu.size()){
  13.         pair<int,pair<int,int>>tmp=qu.front();qu.pop();
  14.         int i=tmp.first,j=tmp.second.first,k=tmp.second.second;
  15.         for(imn=0;imn<=x;imn++){
  16.             if(imn>i)continue;
  17.             for(jmn=0;jmn<=x-imn;jmn++){
  18.                 if(jmn>j)continue;
  19.                 kmn=x-imn-jmn;
  20.                 if(kmn>k)continue;
  21.                 for(ipl=0;ipl<=y;ipl++){
  22.                     if(ipl>i-imn)continue;
  23.                     for(jpl=0;jpl<=y-ipl;jpl++){
  24.                         if(jpl>j-jmn)continue;
  25.                         kpl=y-ipl-jpl;
  26.                         if(kpl>k-kmn)continue;
  27.                         ii=i-ipl-imn+jmn+kpl;
  28.                         jj=j-jpl-jmn+ipl+kmn;
  29.                         kk=k-kpl-kmn+imn+jpl;
  30.                         if(dp[ii][jj][kk]==-1){
  31.                             dp[ii][jj][kk]=dp[i][j][k]+1;
  32.                             qu.push(make_pair(ii,make_pair(jj,kk)));
  33.                         }
  34.                     }
  35.                 }
  36.  
  37.             }
  38.         }
  39.     }
  40.     for(int i=1;i<=q;i++){
  41.         ii=cnt[tv[i].second][0]-cnt[tv[i].first-1][0];
  42.         jj=cnt[tv[i].second][1]-cnt[tv[i].first-1][1];
  43.         kk=cnt[tv[i].second][2]-cnt[tv[i].first-1][2];
  44.         cout<<dp[ii][jj][kk]<<"\n";
  45.     }
  46. }
  47. void init(){
  48.     cin>>n>>q>>x>>y;
  49.     for(int i=1;i<=n;i++){
  50.         int u;
  51.         cin>>u;
  52.         cnt[i][0]=cnt[i-1][0];
  53.         cnt[i][1]=cnt[i-1][1];
  54.         cnt[i][2]=cnt[i-1][2];
  55.         cnt[i][u]++;
  56.     }
  57.     for(int i=1;i<=q;i++){
  58.         cin>>tv[i].first>>tv[i].second;
  59.         vis[tv[i].second-tv[i].first+1]=1;
  60.     }
  61.     dp=new int**[n+1];
  62.     for(int i=0;i<=n;i++){
  63.         dp[i]=new int*[n-i+1];
  64.         for(int j=0;j+i<=n;j++){
  65.             dp[i][j]=new int[n-i-j+1];
  66.             for(int k=0;i+j+k<=n;k++){
  67.                 dp[i][j][k]=-1;
  68.                 if(vis[i]&&j==0&&k==0){
  69.                     dp[i][j][k]=0;
  70.                     qu.push(make_pair(i,make_pair(j,k)));
  71.                 }
  72.             }
  73.         }
  74.     }
  75. }
  76. int main(){
  77.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  78.     freopen("LIGHT.INP","r",stdin);
  79.     freopen("LIGHT.OUT","w",stdout);
  80.     init();
  81.     process();
  82. }
  83.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/hXsWhO
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!