Submission #1267857

#TimeUsernameProblemLanguageResultExecution timeMemory
1267857ducdevFinancial Report (JOI21_financial)C++20
48 / 100
521 ms197304 KiB
// Author: 4uckd3v - Nguyen Cao Duc #include <bits/stdc++.h> using namespace std; #define all(x) (x).begin(), (x).end() typedef long long ll; typedef pair<int, int> ii; const int MAX_N = 3e5; const int MOD = 1e9 + 7; template <class X, class Y> bool maximize(X &x, const Y &y) { if (x >= y) return false; x = y; return true; }; struct FenwickTree { int n; vector<int> bit; void update(int pos, int val) { for (; pos > 0; pos -= pos & (-pos)) bit[pos] += val; }; int get(int pos) { int ret = 0; for (; pos <= n; pos += pos & (-pos)) ret += bit[pos]; return ret; }; FenwickTree(int n) : n(n) { bit.assign(n + 5, 0); }; }; int n, d; int a[MAX_N + 5]; namespace SUBTASK_12 { const int N = 400; int dp[N + 5][N + 5]; void Solve() { for (int i = 0; i <= n; i++) { for (int j = 0; j <= n; j++) { dp[i][j] = 0; }; }; for (int i = 1; i <= n; i++) { dp[i][a[i]] = 1; for (int j = i - 1; j >= max(1, i - d); j--) { for (int mx = a[j]; mx <= n; mx++) { maximize(dp[i][max(mx, a[i])], dp[j][mx] + (a[i] > mx)); }; }; }; int res = 0; for (int mx = a[n]; mx <= n; mx++) maximize(res, dp[n][mx]); cout << res << '\n'; }; }; // namespace SUBTASK_12 namespace SUBTASK_3 { const int N = 7000; int dp[N + 5][N + 5], best[N + 5]; deque<int> dq[N + 5]; void Solve() { for (int i = 0; i <= n; i++) { for (int j = 0; j <= n; j++) { dp[i][j] = 0; }; }; for (int i = 1; i <= n; i++) { dp[i][a[i]] = 1; for (int mx = 0; mx <= n; mx++) best[mx] = 0; for (int mx = 0; mx <= n; mx++) { while (!dq[mx].empty() && dq[mx].front() < max(i - d, 1)) dq[mx].pop_front(); if (!dq[mx].empty()) best[mx] = dp[dq[mx].front()][mx]; }; for (int mx = 0; mx <= n; mx++) { maximize(dp[i][max(mx, a[i])], best[mx] + (a[i] > mx)); }; for (int mx = a[i]; mx <= n; mx++) { while (!dq[mx].empty()) { int j = dq[mx].back(); if (dp[j][mx] <= dp[i][mx]) dq[mx].pop_back(); else break; }; dq[mx].push_back(i); }; }; int res = 0; for (int mx = a[n]; mx <= n; mx++) maximize(res, dp[n][mx]); cout << res << '\n'; }; }; // namespace SUBTASK_3 namespace SUBTASK_4 { const int N = MAX_N; const int D = 1; bool mark[N + 5]; void Solve() { FenwickTree bit(n); int res = 0, curRank; for (int i = n; i >= 1; i--) { curRank = min(bit.get(a[i] + 1), curRank) + 1; maximize(res, curRank); if (!mark[a[i]]) bit.update(a[i], 1); mark[a[i]] = true; }; cout << res << '\n'; }; }; // namespace SUBTASK_4 int main() { ios_base::sync_with_stdio(0); cin.tie(0); if (fopen("MAIN.INP", "r")) { freopen("MAIN.INP", "r", stdin); freopen("MAIN.OUT", "w", stdout); }; cin >> n >> d; vector<ii> v(n); for (int i = 1; i <= n; i++) { cin >> a[i]; v[i - 1] = make_pair(a[i], i); }; sort(all(v)); int cur = 0; for (int i = 0; i < n; i++) { cur += (i == 0 || v[i - 1].first != v[i].first); a[v[i].second] = cur; }; if (n <= 400) return SUBTASK_12::Solve(), 0; if (n <= 7000) return SUBTASK_3::Solve(), 0; if (d == 1) return SUBTASK_4::Solve(), 0; };

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:145:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  145 |         freopen("MAIN.INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:146:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |         freopen("MAIN.OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...