c/c++语言开发共享luogu 黑题 P3724大佬

#include using namespace std; #define ll long long #define RG register #define MAX 111 #define ft(i) (zt[i].first) #define sd(i) (zt[i].second) inline… …

#include<bits/stdc++.h>  using namespace std;  #define ll long long  #define rg register  #define max 111  #define ft(i) (zt[i].first)  #define sd(i) (zt[i].second)  inline int read()  {      rg int x=0,t=1;rg char ch=getchar();      while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();      if(ch=='-')t=-1,ch=getchar();      while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();      return x*t;  }  int f[max][max];  int n,m,mc,day,a[max],w[max],c[max];  struct node{int i,f,l;};  pair<int,int> zt[1111111];  int tot,mx;  int mod=1000007;  struct hash  {      struct line{int x,y,next;}e[1111111];      int h[1000007+1],cnt;      void add(int x,int y)      {          int pos=(1ll*x*101+y)%mod;          e[++cnt]=(line){x,y,h[pos]};h[pos]=cnt;      }      bool query(int x,int y)      {          int pos=(1ll*x*101+y)%mod;          for(int i=h[pos];i;i=e[i].next)              if(e[i].x==x&&e[i].y==y)return true;          return false;      }  }map;  void bfs()  {      queue<node> q;q.push((node){1,1,0});      while(!q.empty())      {          node u=q.front();q.pop();          if(u.i==day)continue;          q.push((node){u.i+1,u.f,u.l+1});          if(u.l>1&&1ll*u.f*u.l<=1ll*mx&&!map.query(u.f*u.l,u.i+1))          {              q.push((node){u.i+1,u.f*u.l,u.l});              zt[++tot]=make_pair(u.f*u.l,u.i+1);              map.add(u.f*u.l,u.i+1);          }      }  }  int main()  {      n=read();m=read();mc=read();      for(int i=1;i<=n;++i)a[i]=read();      for(int i=1;i<=n;++i)w[i]=read();      for(int i=1;i<=m;++i)mx=max(mx,c[i]=read());      for(int i=1;i<=n;++i)          for(int j=a[i];j<=mc;++j)          {              f[i][j-a[i]]=max(f[i-1][j]+1,f[i][j-a[i]]);              f[i][min(j-a[i]+w[i],mc)]=max(f[i-1][j],f[i][min(j-a[i]+w[i],mc)]);          }      for(int i=1;i<=n;++i)          for(int j=1;j<=mc;++j)day=max(day,f[i][j]);      bfs();sort(&zt[1],&zt[tot+1]);      for(int i=1;i<=m;++i)      {          if(c[i]<=day){puts("1");continue;}          bool fl=false;int mm=1e9;          for(int j=tot,k=1;j;--j)          {              while(k<tot&&ft(k)+ft(j)<=c[i])                  mm=min(mm,sd(k)-ft(k)),++k;              if(mm+c[i]-ft(j)<=day-sd(j)){fl=true;break;}              if(ft(j)<=c[i]&&c[i]-ft(j)<=day-sd(j)){fl=true;break;}          }          fl?puts("1"):puts("0");      }      return 0;  }  

  

www.ctvol.com true Article c/c++语言开发共享luogu 黑题 P3724大佬

本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。

ctvol管理联系方式QQ:251552304

本文章地址:https://www.ctvol.com/c-cdevelopment/603158.html

(0)
上一篇 2021年5月11日 下午5:45
下一篇 2021年5月11日 下午5:47

精彩推荐