Submission #654151

#	Time	Username	Problem	Language	Result	Execution time	Memory
654151		Behradm	Financial Report (JOI21_financial)	C++17	65 / 100	4073 ms	8160 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define lc id << 1
#define rc id << 1 | 1
#define sz(x) (int) ((x).size())

const int N = 3e5 + 5, inf = 2e9;
int a[N], dp[N][2], seg[2][N << 2], ans[N], mn[N];
int n;

void Modify(int j, int i, int x, int s = 1, int e = n, int id = 1) {
  if (s == e) {
    seg[j][id] = x;
    return;
  }
  int m = (s + e) >> 1;
  if (i <= m)
    Modify(j, i, x, s, m, lc);
  else
    Modify(j, i, x, m + 1, e, rc);
  seg[j][id] = max(seg[j][lc], seg[j][rc]);
}

int Get(int j, int l, int r, int s = 1, int e = n, int id = 1) {
  if (r < s || e < l)
    return 0;
  if (l <= s && e <= r)
    return seg[j][id];
  int m = (s + e) >> 1;
  return max(Get(j, l, r, s, m, lc), Get(j, l, r, m + 1, e, rc));
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int d;
  cin >> n >> d;
  for (int i = 1; i <= n; i++) mn[i] = inf;
  mn[0] = -inf;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    int j = lower_bound(mn, mn + n + 1, a[i]) - mn;
    mn[j] = a[i];
  }
  a[0] = inf;

  if (d == n) {
    for (int i = n; i >= 0; i--)
      if (mn[i] < inf)
        return cout << i << '\n', 0;
  }

  if (d == 1) {
    vector<int> st;
    st.push_back(0);
    for (int i = 1; i <= n; i++) {
      while (!st.empty() && a[st.back()] < a[i])
        st.pop_back();
      int j = st.back();
      st.push_back(i);
      ans[j + 1]++;
      ans[i + 1]--;
    }
    for (int i = 1; i <= n; i++)
      ans[i] += ans[i - 1];
    cout << *max_element(ans + 1, ans + n + 1) << '\n';
    return 0;
  }


  a[0] = -inf;
  dp[0][0] = dp[0][1] = 0;
  vector<int> st;
  st.push_back(0);
  for (int i = 1; i <= n; i++) {
    int lst = i;
    dp[i][1] = 1;
    for (int j = i - 1; j >= 1; j--) {
      if (a[j] < a[i]) {
        if (lst - j > d)
          break;
        dp[i][1] = max(dp[i][1], dp[j][1] + 1);
        lst = j;
      }
    }
    dp[i][0] = dp[i][1];
    for (int j = i - 1; j >= max(1, i - d); j--)
      dp[i][0] = max(dp[i][0], dp[j][0]);
  }
  cout << dp[n][0] << '\n';
  return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 20 / 20
• Subtask 4: 12 / 12
• Subtask 5: 5 / 5
• Subtask 6: 0 / 35