QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#719360 | #7875. Queue Sorting | Yuanyin26 | TL | 0ms | 5848kb | C++20 | 1.7kb | 2024-11-07 00:24:53 | 2024-11-07 00:24:54 |
Judging History
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 ...