fork download 
  1. #include<bits/stdc++.h>
  2. typedef long long int lli;
  3. using namespace std;
  4. lli dp[20][(1LL<<20)+1];
  5. lli n,tim;
  6. lli dura[20];
  7. vector<lli>st_time[20];
  8.  
  9.  
  10. lli solve(lli idx,lli mask,lli en,lli cnt)
  11. {
  12.    if(en>=tim)
  13.    {
  14.       return 0;
  15.    }
  16.  
  17.    if(dp[idx][mask]!=-1)
  18.    {
  19.       return dp[idx][mask];
  20.    }
  21.  
  22.    lli res=1e18,val,st,i,temp,temp1;
  23.  
  24.    for(i=0;i<n;i++)
  25.    {
  26.       if(mask & (1LL<<i))
  27.       {
  28.          continue;
  29.       }
  30.  
  31.       val=upper_bound(st_time[i].begin(),st_time[i].end(),en)-st_time[i].begin();
  32.       val--;
  33.  
  34.       if(val<0)
  35.       {
  36.          continue;
  37.       }
  38.  
  39.       temp=en;
  40.       st=st_time[i][val];
  41.       temp1=st+dura[i];
  42.  
  43.       if(temp1<=temp)
  44.       {
  45.          continue;
  46.       }
  47.  
  48.       res=min(res,1+solve(i,mask | (1LL<<i),temp1,cnt+1));
  49.    }
  50.  
  51.    return dp[idx][mask]=res;
  52. }
  53.  
  54. int main()
  55. {
  56.    lli i,j,k,m,t,e,ans;
  57.  
  58.    cin>>n>>tim;
  59.  
  60.    for(i=0;i<n;i++)
  61.    {
  62.       cin>>dura[i]>>t;
  63.  
  64.       for(j=0;j<t;j++)
  65.       {
  66.          cin>>e;
  67.          st_time[i].push_back(e);
  68.       }
  69.    }
  70.  
  71.    memset(dp,-1,sizeof(dp));
  72.  
  73.    ans=solve(0,0,0,0);
  74.  
  75.    if(ans>=1e18)
  76.    cout<<-1<<"\n";
  77.    else
  78.    cout<<ans<<"\n";
  79. }
Success #stdin #stdout 0.04s 167508KB
comments (?)
stdin 
Standard input is empty
stdout 
0
https://ideone.com/nTYSdV
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

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!