Submission #24185848

Source Code Expand

#include<iostream>
#include<atcoder/modint>
using namespace std;
using mint=atcoder::modint1000000007;
int N,M;
string S;
int R[3000];
mint dp[3030],ep[3030];
main()
{
	cin>>N>>M>>S;
	for(int i=0;i<M;i++)
	{
		int l,r;cin>>l>>r;
		l--;
		if(R[l]<r)R[l]=r;
	}
	int c0=0,c1=0,nr=0;
	dp[0]=1;
	for(int i=0;i<N;i++)
	{
		int np=0;
		while(nr<=i||nr<R[i])
		{
			if(S[nr]=='0')c0++;
			else np++,c1++;
			nr++;
		}
		for(int j=c1;j>=np;j--)ep[j]=dp[j-np];
		for(int j=0;j<=c1;j++)dp[j]=0;
		for(int j=np;j<=c1;j++)
		{
			if(j>0)dp[j-1]+=ep[j];
			if(c0>i-(c1-j))dp[j]+=ep[j];
		}
	}
	cout<<dp[0].val()<<endl;
}

Submission Info

Submission Time
Task F - Shuffling
User kotatsugame
Language C++ (GCC 9.2.1)
Score 900
Code Size 607 Byte
Status AC
Exec Time 17 ms
Memory 3616 KiB

Compile Error

./Main.cpp:9:6: warning: ISO C++ forbids declaration of ‘main’ with no type [-Wreturn-type]
    9 | main()
      |      ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 900 / 900
Status
AC × 3
AC × 27
Set Name Test Cases
Sample subtask0_0.txt, subtask0_1.txt, subtask0_2.txt
All subtask0_0.txt, subtask0_1.txt, subtask0_2.txt, subtask1_0.txt, subtask1_1.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_2.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_3.txt, subtask1_4.txt, subtask1_5.txt, subtask1_6.txt, subtask1_7.txt, subtask1_8.txt, subtask1_9.txt
Case Name Status Exec Time Memory
subtask0_0.txt AC 3 ms 3488 KiB
subtask0_1.txt AC 2 ms 3604 KiB
subtask0_2.txt AC 2 ms 3572 KiB
subtask1_0.txt AC 12 ms 3612 KiB
subtask1_1.txt AC 15 ms 3504 KiB
subtask1_10.txt AC 17 ms 3560 KiB
subtask1_11.txt AC 13 ms 3500 KiB
subtask1_12.txt AC 16 ms 3516 KiB
subtask1_13.txt AC 13 ms 3508 KiB
subtask1_14.txt AC 13 ms 3508 KiB
subtask1_15.txt AC 14 ms 3508 KiB
subtask1_16.txt AC 12 ms 3504 KiB
subtask1_17.txt AC 14 ms 3508 KiB
subtask1_18.txt AC 15 ms 3508 KiB
subtask1_19.txt AC 13 ms 3524 KiB
subtask1_2.txt AC 16 ms 3564 KiB
subtask1_20.txt AC 15 ms 3492 KiB
subtask1_21.txt AC 13 ms 3616 KiB
subtask1_22.txt AC 14 ms 3500 KiB
subtask1_23.txt AC 15 ms 3616 KiB
subtask1_3.txt AC 13 ms 3612 KiB
subtask1_4.txt AC 12 ms 3468 KiB
subtask1_5.txt AC 16 ms 3616 KiB
subtask1_6.txt AC 13 ms 3616 KiB
subtask1_7.txt AC 15 ms 3580 KiB
subtask1_8.txt AC 12 ms 3524 KiB
subtask1_9.txt AC 13 ms 3504 KiB