Submission #537035

#TimeUsernameProblemLanguageResultExecution timeMemory
537035jamezzzPopeala (CEOI16_popeala)C++17
26 / 100
2082 ms71408 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC optimize("-O3") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #define fi first #define se second #define sf scanf #define pf printf #define INF 1023456789 typedef pair<int,int> ii; int t,n,s,p[20005],r[55][20005],pfx[200005]; ii pv[20005][55]; int dp[55][20005],st[55][20][20005]; char ch[20005]; int main(){ sf("%d%d%d",&n,&t,&s); for(int i=1;i<=t;++i){ sf("%d",&p[i]); pfx[i]=p[i]+pfx[i-1]; } for(int i=0;i<n;++i){ sf(" %s",&ch); for(int j=1;j<=t;++j){ r[i][j]=ch[j-1]-'0'+r[i][j-1]; } } for(int i=1;i<=t;++i){ for(int j=0;j<=n;++j){ //find range with exactly j all 1s int lo=1,hi=i,mid,res=-1,res2=-1; while(lo<=hi){ mid=(lo+hi)/2; int cnt=0; for(int k=0;k<n;++k){ if(r[k][i]-r[k][mid-1]==i-mid+1)++cnt; } if(cnt>=j)res=mid,hi=mid-1; else lo=mid+1; } lo=1,hi=i; while(lo<=hi){ mid=(lo+hi)/2; int cnt=0; for(int k=0;k<n;++k){ if(r[k][i]-r[k][mid-1]==i-mid+1)++cnt; } if(cnt<=j)res2=mid,lo=mid+1; else hi=mid-1; } pv[i][j]={res,res2}; } } for(int i=1;i<=t;++i)dp[0][i]=INF; for(int i=1;i<=s;++i)dp[i][0]=INF; for(int k=1;k<=s;++k){ for(int j=0;j<=n;++j){//how many all 1s for(int i=1;i<=t;++i){//position st[j][0][i]=dp[k-1][i-1]-pfx[i-1]*j; } for(int k=1;k<15;++k){ for(int i=1;i+(1<<k)<=t+1;++i){ st[j][k][i]=min(st[j][k-1][i],st[j][k-1][i+(1<<(k-1))]); } } } for(int i=1;i<=t;++i){ dp[k][i]=INF; for(int j=0;j<=n;++j){//how many all 1s int x=pv[i][j].fi,y=pv[i][j].se; if(x==-1||y==-1||x>y)continue; int l=32-__builtin_clz(y-x+1)-1; dp[k][i]=min(dp[k][i],j*pfx[i]+min(st[j][l][x],st[j][l][y-(1<<l)+1])); } } } for(int i=1;i<=s;++i)pf("%d\n",dp[i][t]); } /* 3 5 5 4 3 5 4 3 10110 11011 00101 */

Compilation message (stderr)

popeala.cpp: In function 'int main()':
popeala.cpp:27:9: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[20005]' [-Wformat=]
   27 |   sf(" %s",&ch);
      |        ~^  ~~~
      |         |  |
      |         |  char (*)[20005]
      |         char*
popeala.cpp:21:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |  sf("%d%d%d",&n,&t,&s);
      |    ^
popeala.cpp:23:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |   sf("%d",&p[i]);
      |     ^
popeala.cpp:27:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |   sf(" %s",&ch);
      |     ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...