Paste Search Dynamic
ans
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3.  
  4. using namespace std;
  5.  
  6. struct op
  7. {
  8.         string type;
  9.         int num;
  10. };
  11.  
  12. int main()
  13. {
  14.         ios_base::sync_with_stdio(0);
  15.         cin.tie(0);
  16.         set <int> all_nums;
  17.  
  18.         int n;
  19.         cin >> n;
  20.         vector <op> ops(n + 1);
  21.  
  22.         for (int i = 1; i <= n; i++)
  23.         {
  24.                 cin >> ops[i].type;
  25.  
  26.                 if (ops[i].type == "+")
  27.                 {
  28.                         cin >> ops[i].num;
  29.                         all_nums.insert(ops[i].num);
  30.                 }
  31.         }
  32.  
  33.         vector <int> sorted_nums;
  34.         map <int, int> ind_of_num;
  35.  
  36.         for (auto x: all_nums)
  37.         {
  38.                 ind_of_num[x] = sorted_nums.size();
  39.                 sorted_nums.push_back(x);
  40.         }
  41.  
  42.         ll mod = 998244353, nums_am = all_nums.size();
  43.         vector <vector <vector <int> > > dp_pref(n + 1);
  44.  
  45.         for (int i = 0; i <= n; i++)
  46.         {
  47.                 dp_pref[i].resize(nums_am);
  48.                 //dp_suff[i].resize(nums_am);
  49.  
  50.                 for (int j = 0; j < nums_am; j++)
  51.                 {
  52.                         dp_pref[i][j].resize(n + 1);
  53.                 //      dp_suff[i][j].resize(n + 1);
  54.                 }
  55.         }
  56.  
  57.         for (int i = 0; i < nums_am; i++)
  58.         {
  59.                 dp_pref[0][i][0] = 1;
  60.  
  61.                 //for (int j = 0; j <= n; j++)
  62.                 //      dp_suff[0][i][j] = 1;
  63.         }
  64.  
  65.         for (int i = 1; i <= n; i++)
  66.                 for (int j = 0; j < nums_am; j++)
  67.                         for (int k = 0; k <= n; k++)
  68.                         {
  69.                                 if (ops[i].type == "-")
  70.                                 {
  71.                                         if (k == 0)
  72.                                                 dp_pref[i][j][k] = (dp_pref[i - 1][j][k] + dp_pref[i - 1][j][k]) % mod;
  73.                                         else
  74.                                                 dp_pref[i][j][k] = (dp_pref[i - 1][j][k] + dp_pref[i - 1][j][min(k + 1, n)]) % mod;
  75.                                 }
  76.                                 else if (ops[i].num <= sorted_nums[j])
  77.                                         dp_pref[i][j][k] = (dp_pref[i - 1][j][k] + dp_pref[i - 1][j][max(k - 1, 0)]) % mod;
  78.                                 else
  79.                                         dp_pref[i][j][k] = (dp_pref[i - 1][j][k] + dp_pref[i - 1][j][k]) % mod;
  80.                         }
  81.  
  82.         vector <vector <int> > dp_pref1(n + 1, vector <int> (n + 1));
  83.  
  84.         for (int i = 1; i <= n; i++)
  85.                 for (int j = 0; j <= n; j++)
  86.                         if (ops[i].type == "+")
  87.                                 dp_pref1[i][j] = dp_pref[i - 1][ind_of_num[ops[i].num]][j];
  88.  
  89.         dp_pref.clear();
  90.  
  91.         vector <vector <vector <int> > > dp_suff(n + 1);
  92.  
  93.         for (int i = 0; i <= n; i++)
  94.         {
  95.                 //dp_pref[i].resize(nums_am);
  96.                 dp_suff[i].resize(nums_am);
  97.  
  98.                 for (int j = 0; j < nums_am; j++)
  99.                 {
  100.                 //      dp_pref[i][j].resize(n + 1);
  101.                         dp_suff[i][j].resize(n + 1);
  102.                 }
  103.         }
  104.  
  105.         for (int i = 0; i < nums_am; i++)
  106.         {
  107.                 //dp_pref[0][i][0] = 1;
  108.  
  109.                 for (int j = 0; j <= n; j++)
  110.                         dp_suff[0][i][j] = 1;
  111.         }
  112.  
  113.  
  114.         for (int i = 1; i <= n; i++)
  115.                 for (int j = 0; j < nums_am; j++)
  116.                         for (int k = 1; k <= n; k++)
  117.                         {
  118.                                 if (ops[n - i + 1].type == "-")
  119.                                 {
  120.                                         if (k == 1)
  121.                                                 dp_suff[i][j][k] = dp_suff[i - 1][j][k];
  122.                                         else
  123.                                                 dp_suff[i][j][k] = (dp_suff[i - 1][j][k] + dp_suff[i - 1][j][k - 1]) % mod;
  124.                                 }
  125.                                 else if (ops[n - i + 1].num < sorted_nums[j])
  126.                                         dp_suff[i][j][k] = (dp_suff[i - 1][j][k] + dp_suff[i - 1][j][min(k + 1 , n)]) % mod;
  127.                                 else
  128.                                         dp_suff[i][j][k] = (dp_suff[i - 1][j][k] + dp_suff[i - 1][j][k]) % mod;
  129.                         }
  130.  
  131.         ll ans = 0;
  132.  
  133.         for (int i = 1; i <= n; i++)
  134.                 if (ops[i].type == "+")
  135.                 {
  136.                         for (int k = 0; k < n; k++)
  137.                         {
  138.                                 ll to_add = dp_pref1[i][k] - dp_pref1[i][k + 1];
  139.                                 to_add = (to_add % mod + mod) % mod;
  140.  
  141.                                 to_add = to_add * dp_suff[n - i][ind_of_num[ops[i].num]][k + 1] % mod;
  142.  
  143.                                 to_add = to_add * ops[i].num % mod;
  144.  
  145.                                 ans = (ans + to_add) % mod;
  146.                         }
  147.                 }
  148.  
  149.         cout << ans;
  150. }
Parsed in 0.021 seconds