Submission #1173761

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173761		Zero_OP	Financial Report (JOI21_financial)	C++20	48 / 100	4093 ms	4932 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define ROF(i, r, l) for(int i = (r)-1; i >= (l); --i)

#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back

#define dbg(x) "[" #x " = " << (x) << "]"

template<typename T>
      bool minimize(T& a, const T& b){
            if(a > b) return a = b, true;
            return false;
      }

template<typename T>
      bool maximize(T& a, const T& b){
            if(a < b) return a = b, true;
            return false;
      }

using ll = long long;
using db = double;
using ull = unsigned long long;
using ld = long double;

using pi = pair<int, int>;
using pl = pair<ll, ll>;

using vi = vector<int>;
using vl = vector<ll>;
using vd = vector<db>;
using vc = vector<char>;
using vb = vector<bool>;

using vpi = vector<pi>;
using vpl = vector<pl>;

using vvi = vector<vi>;
using vvl = vector<vl>;

void setIO(){
      ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
      freopen("task.inp", "r", stdin);
      freopen("task.out", "w", stdout);
#endif // LOCAL
}

//struct SegmentTree{
//      vi mx, tm, lzy;
//      vector<set<pi>> in;
//      SegmentTree(int n) : in(n << 2), mx(n << 2, -inf), tm(n << 2), lzy(n << 2, -1) {}
//
//      void apply_time(int id, int val){
//            tm[id] = val;
//            lazy[id] = val;
//      }
//
//      void push(int id){
//            if(lzy[id] != -1){
//                  apply_time(id << 1, lzy[id]);
//                  apply_time(id << 1 | 1, lzy[id]);
//                  lzy[id] = -1;
//            }
//      }
//
//      void update_time(int id, int l, int r, int u, int v, int val){
//            if(u <= l && r <= v){
//                  apply_time(id, val);
//            } else{
//                  int mid = l + r >> 1;
//                  push(id);
//                  if(u <= mid) update_time(id << 1, l, mid, u, v, val);
//                  if(mid < v)  update_time(id << 1 | 1, mid + 1, r, u, v, val);
//                  pull(id);
//            }
//      }
//};

int main(){
      setIO();

      int N, D;
      cin >> N >> D;
      vi A(N), v;
      FOR(i, 0, N) cin >> A[i];

      v = A;
      sort(all(v)); compact(v);

      vi dp(N), tm(N);
      FOR(i, 0, N){
            dp[i] = 1;
            tm[i] = i;

            FOR(j, 0, i){
                  if(i - tm[j] <= D && A[i] > A[j]) maximize(dp[i], dp[j]+1);
            }

            FOR(j, 0, i){
                  if(i - tm[j] <= D && A[j] >= A[i]) tm[j] = i;
            }

//            FOR(j, 0, i) cout << tm[j] << " \n"[j == i-1];
//            cout << dbg(A[i]) << dbg(dp[i]) << '\n';
      }

      int result = dp[N-1];

      FOR(i, 0, N){
            if(N-1 - tm[i] <= D) maximize(result, dp[i]);
      }

      cout << result << '\n';

      return 0;
}

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