QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#719360#7875. Queue SortingYuanyin26TL 0ms5848kbC++201.7kb2024-11-07 00:24:532024-11-07 00:24:54

Judging History

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

  • [2024-11-07 00:24:54]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:5848kb
  • [2024-11-07 00:24:53]
  • 提交

answer

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<string.h>
#include <string>
#include<math.h>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<map>
#include<queue>
#include<stack>
#include<functional>
#include<deque>
using namespace std;
//#define int long long 
#define inf 1e18
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int N = 505;
const int M = 2e5 + 7;
const int mod = 998244353;
#define PA pair<int,int>
int c[N][N];
int pre[N][N];
void init() {
	for (int i = 0; i < N; ++i)
	{
		pre[i][0] = 1;
		for (int j = 0; j <= i; ++j)
		{
			if (!j) c[i][j] = 1;
			else
			{
				c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
				pre[i][j] = (pre[i][j - 1] + c[i][j])%mod;
			}
		}
	}
		
}

void solve()
{
	int n;
	cin >> n;
	init();
	vector<int>a(n + 1),A(1);
	vector<vector<int>>C(1,{0});
	vector<int>dp(n + 1,0);
	int cnt = 0;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		if (a[i] != 0)
		{
			A.push_back(a[i]);
			cnt++;
		}
	}
	dp[1] = 1;
	for (int i = 1; i <= cnt; i++)
	{
		dp[i] = (dp[i] + dp[i - 1])%mod;
		for (int j = 1; j <= i - 1; j++)
		{
			for (int k = 0; k < C[j].size()-1; k++)
			{
				int kk = min(C[j][k], a[i]);
				dp[i] = (dp[i] + pre[C[j][k]][kk]-1)%mod;
			}
			dp[i] = (dp[i] + 1) % mod;
		}
		for (int j = i; j >=1; j--)
		{
			if (j == i)C.push_back({});
			for (int k = 0; k < C[j-1].size(); k++)
			{
				int tp = C[j - 1][k] + a[i];
				C[j].push_back(tp); 
			}
		}
	}
	cout << dp[cnt] << endl;

}
signed main() {
	IOS;
	int T = 1;//cin >> T;
	while (T--) {
		solve();
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 5848kb

input:

4
1 1 1 1

output:

14

result:

ok 1 number(s): "14"

Test #2:

score: -100
Time Limit Exceeded

input:

300
0 5 2 2 1 0 3 2 2 5 2 1 1 2 1 3 2 3 2 0 0 0 0 1 2 2 3 0 2 2 3 2 0 2 3 0 6 0 0 2 0 1 3 2 1 1 1 3 4 0 1 0 4 1 1 1 1 1 1 2 3 2 1 2 3 2 3 0 5 3 3 2 0 1 1 0 2 1 1 2 0 0 2 1 1 3 2 2 1 2 1 3 0 3 0 1 2 2 0 5 0 2 2 0 0 0 1 2 1 4 2 1 1 0 3 0 2 0 3 1 1 2 0 2 1 1 0 2 0 1 2 2 3 3 1 1 1 1 0 1 3 3 1 0 2 2 4 2 ...

output:


result: