Submission #654157

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
654157	2022-10-30T08:02:41 Z	Shahrad	Financial Report (JOI21_financial)	C++17	17 / 100	160 ms	6836 KB

Main

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define int ll
#define endl '\n'
#define sz size ()
#define all(x) x.begin(),x.end()
#define pb push_back
#define F first
#define S second
#define pii pair<int,int>
#define mk make_pair

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")

const int N = 1e6 + 5;

int a[N];
stack <int> st;
vector <int> vct;
pii dp[N];

int32_t main ()
{
    int n, d;
    cin >> n >> d;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    if (d == 1)
    {
        st.push (a[n - 1]);
        int ans = 1;
        for (int i = n - 2; ~i; i--)
        {
            while (st.sz && a[i] >= st.top ())
                st.pop ();
            st.push (a[i]);
            ans = max (ans, (int) st.sz);
        }
        cout << ans << endl;
    }
    else if (d == n)
    {
        for (int i = 0; i < n; i++)
        {
            int it = lower_bound (all (vct), a[i]) - vct.begin ();
            if (it == vct.sz)
                vct.pb (a[i]);
            else
                vct[it] = a[i];
        }
        cout << vct.sz << endl;
    }
    else
    {
        dp[0] = mk (1, a[0]);
        for (int i = 1; i < n; i++)
            for (int j = max (0ll, i - d); j < i; j++)
                if (dp[i].F < dp[j].F + bool (a[i] > dp[j].S))
                    dp[i] = mk (dp[j].F + bool (a[i] > dp[j].S), max (a[i], dp[j].S));
        cout << dp[n - 1].F << endl;
    }
}

Compilation message

Main.cpp: In function 'int32_t main()':
Main.cpp:49:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |             if (it == vct.sz)
      |                    ^

Subtask #1
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Incorrect	1 ms	212 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #2
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Incorrect	1 ms	212 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #3
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Incorrect	1 ms	212 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #4
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	157 ms	2560 KB	Output is correct
2	Correct	104 ms	2532 KB	Output is correct
3	Correct	114 ms	2604 KB	Output is correct
4	Correct	114 ms	2648 KB	Output is correct
5	Correct	113 ms	2636 KB	Output is correct
6	Correct	114 ms	2600 KB	Output is correct
7	Correct	132 ms	5168 KB	Output is correct
8	Correct	119 ms	2544 KB	Output is correct
9	Correct	110 ms	4232 KB	Output is correct
10	Correct	112 ms	2644 KB	Output is correct
11	Correct	112 ms	2636 KB	Output is correct
12	Correct	121 ms	2604 KB	Output is correct
13	Correct	110 ms	2636 KB	Output is correct
14	Correct	113 ms	2576 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	126 ms	2524 KB	Output is correct
2	Correct	127 ms	2596 KB	Output is correct
3	Correct	124 ms	2564 KB	Output is correct
4	Correct	123 ms	2556 KB	Output is correct
5	Correct	160 ms	3724 KB	Output is correct
6	Correct	128 ms	2676 KB	Output is correct
7	Correct	117 ms	6836 KB	Output is correct
8	Correct	116 ms	2572 KB	Output is correct
9	Correct	145 ms	3736 KB	Output is correct
10	Correct	132 ms	2656 KB	Output is correct
11	Correct	128 ms	2796 KB	Output is correct
12	Correct	144 ms	2544 KB	Output is correct

Subtask #6
0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Incorrect	1 ms	212 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Submission #654157

Compilation message

Subtask #1 0 / 14.0

Subtask #2 0 / 14.0

Subtask #3 0 / 20.0

Subtask #4 12.0 / 12.0

Subtask #5 5.0 / 5.0

Subtask #6 0 / 35.0

Subtask #1
0 / 14.0

Subtask #2
0 / 14.0

Subtask #3
0 / 20.0

Subtask #4
12.0 / 12.0

Subtask #5
5.0 / 5.0

Subtask #6
0 / 35.0