Submission #14500420

---

Source Code Expand

/*
*/

#pragma GCC optimize("O3")
#define _CRT_SECURE_NO_WARNINGS
#include <assert.h>
#include <math.h>
#include <memory.h>
#include <stdio.h>

#include <algorithm>
#include <complex>
#include <ctime>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define y0 sdkfaslhagaklsldk

#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define norm asdfasdgasdgsd
#define left asdgashgrketwjklrej
#define have adsgagshdshfhds
#define ends asdgahhfdsfshdshfd
#define prev asdgSHJsfgsdfhdsh
#define hash asdgasdgasdgdfrywewery

#define eps 1e-12
#define M_PI 3.141592653589793
#define bsize 1024

#define ldouble long double
using namespace std;

#define bs 998244353

const int N = 500031;

string st;
int k;
vector<int> v;
int cnt;
int dp[3][331][331];
int sdp_take[661][661],sdp_drop[661][661];

int main() {
  // freopen("input.txt", "r", stdin);
  // freopen("output.txt", "w", sttextdout);
  ios_base::sync_with_stdio(0);
  // cin.tie(0);

  cin>>st>>k;
  st=st+"0";
  for (int i=0;i<st.size();i++){
	  if (st[i]=='0'){
		  v.push_back(cnt);
		  cnt=0;
	  }
	  else
	  {
		  ++cnt;
	  }
  }

  reverse(v.begin(),v.end());

  dp[0][0][0]=1;

  for (int i=0;i<v.size();i++){

	  for (int j=0;j<=300;j++){
		  for (int q=0;q<=300;q++){
			  dp[1-i%2][j][q]=0;
		  }
	  }

	  for (int j=0;j<=300;j++){
		  for (int q=0;q<=300;q++){
			  sdp_take[j][q]=0;
		  }
	  }

	  for (int j=0;j<=600;j++){
		  for(int q=0;q<=600;q++)
		  {
			  sdp_drop[j][q]=0;
		  }
	  }

	  for (int j=0;j<=300;j++){
		  for (int q=0;q<=300;q++){
			  sdp_drop[j+q][j]=dp[i%2][j][q];
		  }
	  }

	  for (int j=0;j<=600;j++){
		  for (int q=0;q<=600;q++){
			  if (q)
				  sdp_drop[j][q]+=sdp_drop[j][q-1];
			  sdp_drop[j][q]%=bs;
		  }
	  }

	  for (int j=0;j<=300;j++){
		  for (int q=0;q<=300;q++){
			  sdp_take[j][q]=dp[i%2][j][q];
			  if (j)
				  sdp_take[j][q]+=sdp_take[j-1][q];
			  sdp_take[j][q]%=bs;
		  }
	  }

	  for (int new_in_hand=0;new_in_hand<=300;new_in_hand++){
		  for (int new_dif=0;new_dif<=300;new_dif++){
			  // dropped some here, definitely more than 0, at most min(300-new_in_hand,new_dif);
			  int BOUND=min(300-new_in_hand,new_dif);
			  //for (int how_much=1;how_much+new_in_hand<=300&&how_much<=new_dif;how_much++){
				  dp[1-i%2][new_in_hand][new_dif]+=sdp_drop[new_in_hand+new_dif][new_in_hand+BOUND];
				  dp[1-i%2][new_in_hand][new_dif]%=bs;
				  //if (new_in_hand>0)
					  dp[1-i%2][new_in_hand][new_dif]-=sdp_drop[new_in_hand+new_dif][new_in_hand];
				  if (dp[1-i%2][new_in_hand][new_dif]<0)
					  dp[1-i%2][new_in_hand][new_dif]+=bs;

				  //dp[1-i%2][new_in_hand][new_dif]+=dp[i%2][new_in_hand+how_much][new_dif-how_much];
				  //dp[1-i%2][new_in_hand][new_dif]%=bs;
			  //}
			  // took some here, possibly 0, at most min(v[i],new_in_hand)
			  int ways=sdp_take[new_in_hand][new_dif];
			  if (v[i]<new_in_hand)
				  ways-=sdp_take[new_in_hand-v[i]-1][new_dif];
			  if (ways<0)
				  ways+=bs;
			  dp[1-i%2][new_in_hand][new_dif]+=ways;
			  dp[1-i%2][new_in_hand][new_dif]%=bs;
		  }
	  }
	/* for (int in_hand=0;in_hand<=300;in_hand++){
		 for (int total_dif=0;total_dif<=300;total_dif++){
			 if (dp[i%2][in_hand][total_dif]==0)
				 continue;
			 // drop some here
			 for (int to_drop=1;to_drop<=in_hand;to_drop++){
				 dp[1-i%2][in_hand-to_drop][total_dif+to_drop]+=dp[i%2][in_hand][total_dif];
				 dp[1-i%2][in_hand-to_drop][total_dif+to_drop]%=bs;
			 }
			 // take some, possibly 0
			 for (int to_take=0;to_take<=v[i];to_take++){
				 dp[1-i%2][in_hand+to_take][total_dif]+=dp[i%2][in_hand][total_dif];
				 dp[1-i%2][in_hand+to_take][total_dif]%=bs;
			 }
		 }
	 }*/

  }

  int ans=0;

  for (int i=0;i<=k&&i<=300;i++){
	  ans+=dp[v.size()%2][0][i];
	  ans%=bs;
  }

  cout<<ans<<endl;

  cin.get(); cin.get();
  return 0;
}

Submission Info

Compile Error

./Main.cpp:39: warning: "M_PI" redefined
   39 | #define M_PI 3.141592653589793
      | 
In file included from /usr/include/c++/9/cmath:45,
                 from /usr/include/c++/9/math.h:36,
                 from ./Main.cpp:7:
/usr/include/math.h:777: note: this is the location of the previous definition
  777 | # define M_PI  3.14159265358979323846 /* pi */
      | 
./Main.cpp: In function ‘int main()’:
./Main.cpp:64:17: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   64 |   for (int i=0;i<st.size();i++){
      |                ~^~~~~~~~~~
./Main.cpp:79:17: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   79 |   for (int i=0;i<v.size();i++){
      |                ~^~~~~~~~~

Judge Result