Submission #763720

#	Time	Username	Problem	Language	Result	Execution time	Memory
763720		ind1v	Financial Report (JOI21_financial)	C++11	65 / 100	91 ms	3852 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int N = 300005;

int n, d;
int a[N];

namespace sub3 {
  bool valid_input() {
    return n <= 7000;
  }
  
  int dp[7005];
  
  void solve() {
    for (int i = 1; i <= n; i++) {
      dp[i] = 1;
      int pos = max(1, i - d);
      for (int j = i - 1; j >= pos; j--) {
        if (a[i] > a[j]) {
          dp[i] = max(dp[i], dp[j] + 1);
          pos = min(pos, max(1, j - d));
        }
      }
    }
    cout << *max_element(dp + 1, dp + n + 1);
    exit(0);
  }
}

namespace sub4 {
  bool valid_input() {
    return d == 1;
  }
  
  void solve() {
    int ans = 0;
    stack<int> st;
    for (int i = n; i >= 1; i--) {
      while (!st.empty() && a[st.top()] <= a[i]) {
        st.pop();
      }
      st.push(i);
      ans = max(ans, (int) st.size());
    }
    cout << ans;
    exit(0);
  }
}

namespace sub5 {
  bool valid_input() {
    return d == n;
  }
  
  struct fenwick_tree {
    int fenw[N];
    
    fenwick_tree() {
      memset(fenw, 0, sizeof(fenw));
    }
    
    
    void upd(int idx, int val) {
      for (; idx < N; idx |= (idx + 1)) {
        fenw[idx] = max(fenw[idx], val);
      }
    }
    
    int get(int idx) {
      int res = 0;
      for (; idx >= 0; idx &= (idx + 1), --idx) {
        res = max(res, fenw[idx]);
      }
      return res;
    }
  };
  
  fenwick_tree f;
  
  void solve() {
    vector<int> vals(a + 1, a + n + 1);
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    for (int i = 1; i <= n; i++) {
      a[i] = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin();
      f.upd(a[i], 1 + f.get(a[i] - 1));
    }
    cout << *max_element(f.fenw, f.fenw + N);
    exit(0);
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> d;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  if (sub3::valid_input()) sub3::solve();
  if (sub4::valid_input()) sub4::solve();
  if (sub5::valid_input()) sub5::solve();
  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