QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#593141#7883. Takeout Deliveringforgive_WA 0ms10144kbC++142.0kb2024-09-27 11:55:392024-09-27 11:55:40

Judging History

你现在查看的是最新测评结果

  • [2024-09-27 11:55:40]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:10144kb
  • [2024-09-27 11:55:39]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std ;

typedef long long LL ;
const int N = 510 , mod = 998244353 ;

int n , a[N] , S[N] ;
LL dp[2][N][N] , tmp[N][N] , sum[2][N][N] ;
 
int main()
{
	scanf("%d" , &n ) ;
//	if( n == 300 ) {
//		cout << 507010274 ;
//		return 0 ;
//	}
	for(int i = 1 ; i <= n ; i ++ ) {
		scanf("%d" , &a[i] ) ;
		if( a[i] == 0 ) {
			i -- ; n -- ;
			continue ;
		}
		S[i] = S[i-1] + a[i] ;
	}
	dp[S[1]&1][S[1]][0] = 1 ;
//	sum[S[1]&1][S[1]][0] = 1 ;
	for(int k = 0 ; k < S[1] ; k ++ ) {
		sum[S[1]&1][S[1]][k] = ( (k?sum[S[1]&1][S[1]][k-1]:0) + dp[S[1]&1][S[1]][k] ) % mod ;
	}
	int now = 2 ;//种类 
	tmp[S[2]][0] = 1 ;
//	cout << tmp[3][0] << " lk" << endl ;
	for(int i = S[1]+1 ; i <= S[n] ; i ++ ) {
		int num = S[now]-i ;
		// 全部放到结尾
		for(int j = 1 ; j <= S[now] ; j ++ ) {
			for(int k = 1 ; k < j ; k ++ ) {
				dp[i&1][j][k] = 0 ;
				dp[i&1][j][k] = sum[(i-1)&1][j-1][k-1] ;
//				for(int p = 0 ; p <= k-1 ; p ++ ) {
//					dp[i&1][j][k] = ( dp[i&1][j][k] + dp[(i-1)&1][j-1][p] ) % mod ;
//				}
//				printf("dp[%d][%d][%d] = %lld\n" , i , j , k , dp[i][j][k] ) ;
				// 这num个放到结尾 
				tmp[j+num-k][0] = ( tmp[j+num-k][0] + dp[i&1][j][k] ) % mod ;
				sum[i&1][j][k] = ( sum[i&1][j][k-1] + dp[i&1][j][k] ) % mod ;
			}
		}
		if( i == S[now] ) {
			memcpy( dp[i&1] , tmp , sizeof tmp ) ;
			for(int j = 1 ; j <= S[now] ; j ++ ) {
				for(int k = 0 ; k < j ; k ++ ) {
					sum[i&1][j][k] = ( (k?sum[i&1][j][k-1]:0) + dp[i&1][j][k] ) % mod ;
				}
			}
			memset( tmp , 0 , sizeof tmp ) ;
			now ++ ;
			if( a[now] ) { // 直接考虑 a[now] 个全放到结尾 
				for(int j = 1 ; j <= S[now-1] ; j ++ ) {
					tmp[j+a[now]][0] = ( tmp[j+a[now]][0] + dp[i&1][j][0] ) % mod ;
				}
			}
		}
	}
	LL ans = 0 ;
	for(int j = 0 ; j <= S[n] ; j ++ ) {
//		printf("Ans: dp[%d][%d][%d] = %lld\n" , S[n] , j , 0 , dp[S[n]][j][0] ) ;
		ans = ( ans + dp[S[n]&1][j][0] ) % mod ;
	} 
	printf("%lld" , ans ) ;
	return 0 ;
}
/*
2
2 2 
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 10144kb

input:

4 6
1 2 2
1 3 4
1 4 7
2 3 1
2 4 3
3 4 9

output:

1517

result:

wrong answer 1st numbers differ - expected: '5', found: '1517'