oj.uz

Submission #892167

# Submission time Handle Problem Language Result Execution time Memory
892167 2023-12-25T02:55:34 Z therealpain Financial Report (JOI21_financial) C++17
65 / 100
 715 ms 201044 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define getbit(x) (((x) >> (i)) & 1)
#define TASK ""

using namespace std;

template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
    if (a < b) a = b; else return false; return true;
}

template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
    if (a > b) a = b; else return false; return true;
}

const long long inf = 1e18;
const int mod = 1e9 + 7;
const int N = 3e5 + 5;

int n;
int d;
int a[N];

namespace subtask2 {
    int dp[405][405];
    vector <int> value;

    void solve() {
        for (int i = 1; i <= n; ++i) value.push_back(a[i]);

        sort(all(value));
        value.erase(unique(all(value)), value.end());
        int m = (int) value.size();

        for (int i = 1; i <= n; ++i) {
            a[i] = lower_bound(all(value), a[i]) - value.begin() + 1;
        }

        memset(dp, -0x3f, sizeof dp);

        for (int i = 1; i <= n; ++i) dp[i][a[i]] = 1;

        for (int i = 1; i <= n; ++i) {
            for (int j = i - 1; j >= max(i - d, 1); --j) {
                for (int mx = 1; mx <= m; ++mx) {
                    maxi(dp[i][max(mx, a[i])], dp[j][mx] + (mx < a[i]));
                }
            }
        }

        cout << *max_element(dp[n] + 1, dp[n] + m + 1);
    }
};

namespace subtask3 {
    vector <int> value;
    int dp[7005][7005];
    deque <int> dq[7005];

    void solve() {
        for (int i = 1; i <= n; ++i) value.push_back(a[i]);

        sort(all(value));
        value.erase(unique(all(value)), value.end());
        int m = (int) value.size();

        for (int i = 1; i <= n; ++i) {
            a[i] = lower_bound(all(value), a[i]) - value.begin() + 1;
        }

        memset(dp, -0x3f, sizeof dp);

        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                while (dq[j].size() && dq[j].front() + d < i) dq[j].pop_front();

                if (dq[j].size()) maxi(dp[i][max(a[i], j)], dp[dq[j].front()][j] + (a[i] > j));

                while (dq[max(j, a[i])].size() && dp[dq[max(j, a[i])].back()][max(j, a[i])] <= dp[i][j])
                    dq[max(j, a[i])].pop_back();

                dq[max(a[i], j)].push_back(i);

            }

            maxi(dp[i][a[i]], 1);
            dq[a[i]].push_back(i);
        }


        //for (int i = 1; i <= n; ++i)

        cout << *max_element(dp[n] + 1, dp[n] + m + 1);
    }
};

namespace subtask4 {
    stack <int> st;

    void solve() {
        int ans = 0;
        for (int i = n; i >= 1; --i) {
            while (st.size() && st.top() <= a[i]) st.pop();
            st.push(a[i]);
            maxi(ans, st.size());
        }
        cout << ans;
    }
};

namespace subtask5 {
    void solve() {
        vector <int> dp;

        for (int i = 1; i <= n; ++i) {
            int p = lower_bound(all(dp), a[i]) - dp.begin();
            if (p == dp.size()) dp.push_back(a[i]);
            else dp[p] = a[i];
        }

        cout << (int) dp.size() << '\n';
    }
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);
    cin >> n >> d;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    if (n <= 400) subtask2::solve();
    else if (n <= 7000) subtask3::solve();
    else if (d == 1) subtask4::solve();
    else if (d == n) subtask5::solve();
}

Compilation message

Main.cpp: In function 'void subtask5::solve()':
Main.cpp:119:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |             if (p == dp.size()) dp.push_back(a[i]);
      |                 ~~^~~~~~~~~~~~
Main.cpp: In instantiation of 'bool maxi(T1&, T2) [with T1 = int; T2 = long unsigned int]':
Main.cpp:107:32:   required from here
Main.cpp:11:11: warning: comparison of integer expressions of different signedness: 'int' and 'long unsigned int' [-Wsign-compare]
   11 |     if (a < b) a = b; else return false; return true;
      |         ~~^~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9052 KB Output is correct
2 Correct 2 ms 9052 KB Output is correct
3 Correct 3 ms 9052 KB Output is correct
4 Correct 2 ms 9048 KB Output is correct
5 Correct 3 ms 9052 KB Output is correct
6 Correct 2 ms 9052 KB Output is correct
7 Correct 3 ms 9052 KB Output is correct
8 Correct 3 ms 9052 KB Output is correct
9 Correct 3 ms 9052 KB Output is correct
10 Correct 3 ms 9304 KB Output is correct
11 Correct 3 ms 9048 KB Output is correct
12 Correct 2 ms 9052 KB Output is correct
13 Correct 3 ms 9052 KB Output is correct
14 Correct 3 ms 9052 KB Output is correct
15 Correct 3 ms 9052 KB Output is correct
16 Correct 3 ms 9052 KB Output is correct
17 Correct 3 ms 9052 KB Output is correct
18 Correct 3 ms 9052 KB Output is correct
19 Correct 2 ms 9052 KB Output is correct
20 Correct 2 ms 9052 KB Output is correct
21 Correct 2 ms 9052 KB Output is correct
22 Correct 3 ms 9052 KB Output is correct
23 Correct 3 ms 9052 KB Output is correct
24 Correct 3 ms 9052 KB Output is correct
25 Correct 3 ms 9052 KB Output is correct
26 Correct 3 ms 9052 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9052 KB Output is correct
2 Correct 2 ms 9052 KB Output is correct
3 Correct 3 ms 9052 KB Output is correct
4 Correct 2 ms 9048 KB Output is correct
5 Correct 3 ms 9052 KB Output is correct
6 Correct 2 ms 9052 KB Output is correct
7 Correct 3 ms 9052 KB Output is correct
8 Correct 3 ms 9052 KB Output is correct
9 Correct 3 ms 9052 KB Output is correct
10 Correct 3 ms 9304 KB Output is correct
11 Correct 3 ms 9048 KB Output is correct
12 Correct 2 ms 9052 KB Output is correct
13 Correct 3 ms 9052 KB Output is correct
14 Correct 3 ms 9052 KB Output is correct
15 Correct 3 ms 9052 KB Output is correct
16 Correct 3 ms 9052 KB Output is correct
17 Correct 3 ms 9052 KB Output is correct
18 Correct 3 ms 9052 KB Output is correct
19 Correct 2 ms 9052 KB Output is correct
20 Correct 2 ms 9052 KB Output is correct
21 Correct 2 ms 9052 KB Output is correct
22 Correct 3 ms 9052 KB Output is correct
23 Correct 3 ms 9052 KB Output is correct
24 Correct 3 ms 9052 KB Output is correct
25 Correct 3 ms 9052 KB Output is correct
26 Correct 3 ms 9052 KB Output is correct
27 Correct 3 ms 9052 KB Output is correct
28 Correct 4 ms 9048 KB Output is correct
29 Correct 3 ms 9052 KB Output is correct
30 Correct 5 ms 9096 KB Output is correct
31 Correct 3 ms 9052 KB Output is correct
32 Correct 39 ms 9052 KB Output is correct
33 Correct 3 ms 9052 KB Output is correct
34 Correct 4 ms 9052 KB Output is correct
35 Correct 4 ms 9048 KB Output is correct
36 Correct 10 ms 9048 KB Output is correct
37 Correct 4 ms 9048 KB Output is correct
38 Correct 4 ms 9052 KB Output is correct
39 Correct 6 ms 9096 KB Output is correct
40 Correct 7 ms 9048 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9052 KB Output is correct
2 Correct 2 ms 9052 KB Output is correct
3 Correct 3 ms 9052 KB Output is correct
4 Correct 2 ms 9048 KB Output is correct
5 Correct 3 ms 9052 KB Output is correct
6 Correct 2 ms 9052 KB Output is correct
7 Correct 3 ms 9052 KB Output is correct
8 Correct 3 ms 9052 KB Output is correct
9 Correct 3 ms 9052 KB Output is correct
10 Correct 3 ms 9304 KB Output is correct
11 Correct 3 ms 9048 KB Output is correct
12 Correct 2 ms 9052 KB Output is correct
13 Correct 3 ms 9052 KB Output is correct
14 Correct 3 ms 9052 KB Output is correct
15 Correct 3 ms 9052 KB Output is correct
16 Correct 3 ms 9052 KB Output is correct
17 Correct 3 ms 9052 KB Output is correct
18 Correct 3 ms 9052 KB Output is correct
19 Correct 2 ms 9052 KB Output is correct
20 Correct 2 ms 9052 KB Output is correct
21 Correct 2 ms 9052 KB Output is correct
22 Correct 3 ms 9052 KB Output is correct
23 Correct 3 ms 9052 KB Output is correct
24 Correct 3 ms 9052 KB Output is correct
25 Correct 3 ms 9052 KB Output is correct
26 Correct 3 ms 9052 KB Output is correct
27 Correct 3 ms 9052 KB Output is correct
28 Correct 4 ms 9048 KB Output is correct
29 Correct 3 ms 9052 KB Output is correct
30 Correct 5 ms 9096 KB Output is correct
31 Correct 3 ms 9052 KB Output is correct
32 Correct 39 ms 9052 KB Output is correct
33 Correct 3 ms 9052 KB Output is correct
34 Correct 4 ms 9052 KB Output is correct
35 Correct 4 ms 9048 KB Output is correct
36 Correct 10 ms 9048 KB Output is correct
37 Correct 4 ms 9048 KB Output is correct
38 Correct 4 ms 9052 KB Output is correct
39 Correct 6 ms 9096 KB Output is correct
40 Correct 7 ms 9048 KB Output is correct
41 Correct 168 ms 197764 KB Output is correct
42 Correct 651 ms 199520 KB Output is correct
43 Correct 26 ms 197716 KB Output is correct
44 Correct 259 ms 198264 KB Output is correct
45 Correct 284 ms 198664 KB Output is correct
46 Correct 715 ms 200992 KB Output is correct
47 Correct 581 ms 198996 KB Output is correct
48 Correct 625 ms 200428 KB Output is correct
49 Correct 691 ms 200588 KB Output is correct
50 Correct 654 ms 199764 KB Output is correct
51 Correct 588 ms 197820 KB Output is correct
52 Correct 602 ms 198596 KB Output is correct
53 Correct 558 ms 197972 KB Output is correct
54 Correct 569 ms 197712 KB Output is correct
55 Correct 687 ms 200912 KB Output is correct
56 Correct 674 ms 200896 KB Output is correct
57 Correct 691 ms 201040 KB Output is correct
58 Correct 645 ms 201044 KB Output is correct
59 Correct 631 ms 201044 KB Output is correct
60 Correct 650 ms 200636 KB Output is correct
61 Correct 597 ms 200784 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 10076 KB Output is correct
2 Correct 27 ms 10072 KB Output is correct
3 Correct 28 ms 9816 KB Output is correct
4 Correct 29 ms 10064 KB Output is correct
5 Correct 27 ms 9820 KB Output is correct
6 Correct 27 ms 9820 KB Output is correct
7 Correct 34 ms 11232 KB Output is correct
8 Correct 26 ms 9816 KB Output is correct
9 Correct 27 ms 10840 KB Output is correct
10 Correct 29 ms 10044 KB Output is correct
11 Correct 29 ms 9820 KB Output is correct
12 Correct 27 ms 9816 KB Output is correct
13 Correct 27 ms 9820 KB Output is correct
14 Correct 26 ms 9808 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 10076 KB Output is correct
2 Correct 36 ms 9812 KB Output is correct
3 Correct 40 ms 10076 KB Output is correct
4 Correct 40 ms 10072 KB Output is correct
5 Correct 40 ms 10728 KB Output is correct
6 Correct 39 ms 10064 KB Output is correct
7 Correct 30 ms 12240 KB Output is correct
8 Correct 25 ms 10076 KB Output is correct
9 Correct 32 ms 10704 KB Output is correct
10 Correct 36 ms 10068 KB Output is correct
11 Correct 39 ms 10064 KB Output is correct
12 Correct 27 ms 10076 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9052 KB Output is correct
2 Correct 2 ms 9052 KB Output is correct
3 Correct 3 ms 9052 KB Output is correct
4 Correct 2 ms 9048 KB Output is correct
5 Correct 3 ms 9052 KB Output is correct
6 Correct 2 ms 9052 KB Output is correct
7 Correct 3 ms 9052 KB Output is correct
8 Correct 3 ms 9052 KB Output is correct
9 Correct 3 ms 9052 KB Output is correct
10 Correct 3 ms 9304 KB Output is correct
11 Correct 3 ms 9048 KB Output is correct
12 Correct 2 ms 9052 KB Output is correct
13 Correct 3 ms 9052 KB Output is correct
14 Correct 3 ms 9052 KB Output is correct
15 Correct 3 ms 9052 KB Output is correct
16 Correct 3 ms 9052 KB Output is correct
17 Correct 3 ms 9052 KB Output is correct
18 Correct 3 ms 9052 KB Output is correct
19 Correct 2 ms 9052 KB Output is correct
20 Correct 2 ms 9052 KB Output is correct
21 Correct 2 ms 9052 KB Output is correct
22 Correct 3 ms 9052 KB Output is correct
23 Correct 3 ms 9052 KB Output is correct
24 Correct 3 ms 9052 KB Output is correct
25 Correct 3 ms 9052 KB Output is correct
26 Correct 3 ms 9052 KB Output is correct
27 Correct 3 ms 9052 KB Output is correct
28 Correct 4 ms 9048 KB Output is correct
29 Correct 3 ms 9052 KB Output is correct
30 Correct 5 ms 9096 KB Output is correct
31 Correct 3 ms 9052 KB Output is correct
32 Correct 39 ms 9052 KB Output is correct
33 Correct 3 ms 9052 KB Output is correct
34 Correct 4 ms 9052 KB Output is correct
35 Correct 4 ms 9048 KB Output is correct
36 Correct 10 ms 9048 KB Output is correct
37 Correct 4 ms 9048 KB Output is correct
38 Correct 4 ms 9052 KB Output is correct
39 Correct 6 ms 9096 KB Output is correct
40 Correct 7 ms 9048 KB Output is correct
41 Correct 168 ms 197764 KB Output is correct
42 Correct 651 ms 199520 KB Output is correct
43 Correct 26 ms 197716 KB Output is correct
44 Correct 259 ms 198264 KB Output is correct
45 Correct 284 ms 198664 KB Output is correct
46 Correct 715 ms 200992 KB Output is correct
47 Correct 581 ms 198996 KB Output is correct
48 Correct 625 ms 200428 KB Output is correct
49 Correct 691 ms 200588 KB Output is correct
50 Correct 654 ms 199764 KB Output is correct
51 Correct 588 ms 197820 KB Output is correct
52 Correct 602 ms 198596 KB Output is correct
53 Correct 558 ms 197972 KB Output is correct
54 Correct 569 ms 197712 KB Output is correct
55 Correct 687 ms 200912 KB Output is correct
56 Correct 674 ms 200896 KB Output is correct
57 Correct 691 ms 201040 KB Output is correct
58 Correct 645 ms 201044 KB Output is correct
59 Correct 631 ms 201044 KB Output is correct
60 Correct 650 ms 200636 KB Output is correct
61 Correct 597 ms 200784 KB Output is correct
62 Correct 30 ms 10076 KB Output is correct
63 Correct 27 ms 10072 KB Output is correct
64 Correct 28 ms 9816 KB Output is correct
65 Correct 29 ms 10064 KB Output is correct
66 Correct 27 ms 9820 KB Output is correct
67 Correct 27 ms 9820 KB Output is correct
68 Correct 34 ms 11232 KB Output is correct
69 Correct 26 ms 9816 KB Output is correct
70 Correct 27 ms 10840 KB Output is correct
71 Correct 29 ms 10044 KB Output is correct
72 Correct 29 ms 9820 KB Output is correct
73 Correct 27 ms 9816 KB Output is correct
74 Correct 27 ms 9820 KB Output is correct
75 Correct 26 ms 9808 KB Output is correct
76 Correct 26 ms 10076 KB Output is correct
77 Correct 36 ms 9812 KB Output is correct
78 Correct 40 ms 10076 KB Output is correct
79 Correct 40 ms 10072 KB Output is correct
80 Correct 40 ms 10728 KB Output is correct
81 Correct 39 ms 10064 KB Output is correct
82 Correct 30 ms 12240 KB Output is correct
83 Correct 25 ms 10076 KB Output is correct
84 Correct 32 ms 10704 KB Output is correct
85 Correct 36 ms 10068 KB Output is correct
86 Correct 39 ms 10064 KB Output is correct
87 Correct 27 ms 10076 KB Output is correct
88 Incorrect 25 ms 12880 KB Output isn't correct
89 Halted 0 ms 0 KB -