# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
815149 | 2023-08-08T12:43:13 Z | RecursiveCo | Financial Report (JOI21_financial) | C++14 | 4000 ms | 82444 KB |
// CF template, version 3.0 #include <bits/stdc++.h> using namespace std; #define improvePerformance ios_base::sync_with_stdio(false); cin.tie(0) #define getTest int t; cin >> t #define eachTest for (int _var=0;_var<t;_var++) #define get(name) int (name); cin >> (name) #define out(o) cout << (o) #define getList(cnt, name) vector<int> (name); for (int _=0;_<(cnt);_++) { get(a); (name).push_back(a); } #define sortl(name) sort((name).begin(), (name).end()) #define rev(name) reverse((name).begin(), (name).end()) #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++) #define decision(b) if (b){out("YES");}else{out("NO");} #define int long long int int query(vector<vector<int>>& sparse, int l, int r) { int sz = r - l + 1; int lg = 0; int p = 1; while (p <= sz) { p *= 2; lg++; } p /= 2; lg--; int left = sparse[l][lg]; int right = sparse[r - p + 1][lg]; return max(left, right); } signed main() { improvePerformance; get(n); get(d); getList(n, nums); vector<int> minimums(n, 1e18); multiset<int> window; forto(d, i) window.insert(nums[n - i - 1]); for (int i = n - 1; i >= d - 1; i--) { minimums[i] = *window.begin(); window.erase(window.find(nums[i])); if (i != d - 1) window.insert(nums[i - d]); } vector<vector<int>> sparse(n, vector<int>(19, 0)); for (int i = n - 1; i >= 0; i--) { sparse[i][0] = minimums[i]; int p = 2; forto(19, j) { if (j == 0) continue; if (i + p > n) break; sparse[i][j] = max(sparse[i][j - 1], sparse[i + p / 2][j - 1]); p *= 2; } } vector<int> dp; forto(n, i) dp.push_back(0); int prefmax = 0; for (int i = n - 1; i >= 0; i--) { if (prefmax < nums[i]) { dp[i] = 1; } else { // what's the smallest index j such that j >= i+d and minimums[j] > a[i]? // then we can take any element in between. // (sparse table for the first part) // what about the second part, "taking any element in between"? int l = min(i + d, n); int r = n; while (r - l >= 1) { int middle = (l + r) / 2; if (query(sparse, i + d, middle) <= nums[i]) l = middle + 1; else r = middle; } // inefficient for now int maximum = 0; for (int j = i + 1; j <= l; j++) { if (nums[j] > nums[i]) maximum = max(maximum, dp[j]); } dp[i] = maximum + 1; } prefmax = max(prefmax, nums[i]); } out(*max_element(dp.begin(), dp.end())); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | 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 | 1 ms | 212 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Correct | 1 ms | 212 KB | Output is correct |
7 | Correct | 1 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 | 0 ms | 320 KB | Output is correct |
11 | Correct | 0 ms | 212 KB | Output is correct |
12 | Correct | 0 ms | 212 KB | Output is correct |
13 | Correct | 0 ms | 212 KB | Output is correct |
14 | Correct | 0 ms | 212 KB | Output is correct |
15 | Correct | 1 ms | 212 KB | Output is correct |
16 | Correct | 1 ms | 212 KB | Output is correct |
17 | Correct | 1 ms | 212 KB | Output is correct |
18 | Correct | 0 ms | 212 KB | Output is correct |
19 | Correct | 0 ms | 212 KB | Output is correct |
20 | Correct | 1 ms | 212 KB | Output is correct |
21 | Correct | 0 ms | 212 KB | Output is correct |
22 | Correct | 0 ms | 212 KB | Output is correct |
23 | Correct | 0 ms | 212 KB | Output is correct |
24 | Correct | 0 ms | 212 KB | Output is correct |
25 | Correct | 0 ms | 320 KB | Output is correct |
26 | Correct | 1 ms | 212 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | 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 | 1 ms | 212 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Correct | 1 ms | 212 KB | Output is correct |
7 | Correct | 1 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 | 0 ms | 320 KB | Output is correct |
11 | Correct | 0 ms | 212 KB | Output is correct |
12 | Correct | 0 ms | 212 KB | Output is correct |
13 | Correct | 0 ms | 212 KB | Output is correct |
14 | Correct | 0 ms | 212 KB | Output is correct |
15 | Correct | 1 ms | 212 KB | Output is correct |
16 | Correct | 1 ms | 212 KB | Output is correct |
17 | Correct | 1 ms | 212 KB | Output is correct |
18 | Correct | 0 ms | 212 KB | Output is correct |
19 | Correct | 0 ms | 212 KB | Output is correct |
20 | Correct | 1 ms | 212 KB | Output is correct |
21 | Correct | 0 ms | 212 KB | Output is correct |
22 | Correct | 0 ms | 212 KB | Output is correct |
23 | Correct | 0 ms | 212 KB | Output is correct |
24 | Correct | 0 ms | 212 KB | Output is correct |
25 | Correct | 0 ms | 320 KB | Output is correct |
26 | Correct | 1 ms | 212 KB | Output is correct |
27 | Correct | 0 ms | 320 KB | Output is correct |
28 | Correct | 1 ms | 340 KB | Output is correct |
29 | Correct | 1 ms | 340 KB | Output is correct |
30 | Correct | 1 ms | 340 KB | Output is correct |
31 | Correct | 1 ms | 324 KB | Output is correct |
32 | Correct | 1 ms | 340 KB | Output is correct |
33 | Correct | 1 ms | 340 KB | Output is correct |
34 | Correct | 1 ms | 324 KB | Output is correct |
35 | Correct | 1 ms | 340 KB | Output is correct |
36 | Correct | 1 ms | 316 KB | Output is correct |
37 | Correct | 1 ms | 340 KB | Output is correct |
38 | Correct | 1 ms | 340 KB | Output is correct |
39 | Correct | 1 ms | 340 KB | Output is correct |
40 | Correct | 1 ms | 340 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | 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 | 1 ms | 212 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Correct | 1 ms | 212 KB | Output is correct |
7 | Correct | 1 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 | 0 ms | 320 KB | Output is correct |
11 | Correct | 0 ms | 212 KB | Output is correct |
12 | Correct | 0 ms | 212 KB | Output is correct |
13 | Correct | 0 ms | 212 KB | Output is correct |
14 | Correct | 0 ms | 212 KB | Output is correct |
15 | Correct | 1 ms | 212 KB | Output is correct |
16 | Correct | 1 ms | 212 KB | Output is correct |
17 | Correct | 1 ms | 212 KB | Output is correct |
18 | Correct | 0 ms | 212 KB | Output is correct |
19 | Correct | 0 ms | 212 KB | Output is correct |
20 | Correct | 1 ms | 212 KB | Output is correct |
21 | Correct | 0 ms | 212 KB | Output is correct |
22 | Correct | 0 ms | 212 KB | Output is correct |
23 | Correct | 0 ms | 212 KB | Output is correct |
24 | Correct | 0 ms | 212 KB | Output is correct |
25 | Correct | 0 ms | 320 KB | Output is correct |
26 | Correct | 1 ms | 212 KB | Output is correct |
27 | Correct | 0 ms | 320 KB | Output is correct |
28 | Correct | 1 ms | 340 KB | Output is correct |
29 | Correct | 1 ms | 340 KB | Output is correct |
30 | Correct | 1 ms | 340 KB | Output is correct |
31 | Correct | 1 ms | 324 KB | Output is correct |
32 | Correct | 1 ms | 340 KB | Output is correct |
33 | Correct | 1 ms | 340 KB | Output is correct |
34 | Correct | 1 ms | 324 KB | Output is correct |
35 | Correct | 1 ms | 340 KB | Output is correct |
36 | Correct | 1 ms | 316 KB | Output is correct |
37 | Correct | 1 ms | 340 KB | Output is correct |
38 | Correct | 1 ms | 340 KB | Output is correct |
39 | Correct | 1 ms | 340 KB | Output is correct |
40 | Correct | 1 ms | 340 KB | Output is correct |
41 | Correct | 3 ms | 1876 KB | Output is correct |
42 | Correct | 4 ms | 1816 KB | Output is correct |
43 | Correct | 9 ms | 1876 KB | Output is correct |
44 | Correct | 39 ms | 1688 KB | Output is correct |
45 | Correct | 62 ms | 1748 KB | Output is correct |
46 | Correct | 66 ms | 2208 KB | Output is correct |
47 | Correct | 5 ms | 1736 KB | Output is correct |
48 | Correct | 17 ms | 1736 KB | Output is correct |
49 | Correct | 28 ms | 1860 KB | Output is correct |
50 | Correct | 32 ms | 1876 KB | Output is correct |
51 | Correct | 3 ms | 1876 KB | Output is correct |
52 | Correct | 4 ms | 1876 KB | Output is correct |
53 | Correct | 3 ms | 1876 KB | Output is correct |
54 | Correct | 5 ms | 1876 KB | Output is correct |
55 | Correct | 56 ms | 1876 KB | Output is correct |
56 | Correct | 34 ms | 1884 KB | Output is correct |
57 | Correct | 34 ms | 1876 KB | Output is correct |
58 | Correct | 3 ms | 2132 KB | Output is correct |
59 | Correct | 3 ms | 2120 KB | Output is correct |
60 | Correct | 22 ms | 1736 KB | Output is correct |
61 | Correct | 22 ms | 1868 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 4024 ms | 68080 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 4046 ms | 82444 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | 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 | 1 ms | 212 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Correct | 1 ms | 212 KB | Output is correct |
7 | Correct | 1 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 | 0 ms | 320 KB | Output is correct |
11 | Correct | 0 ms | 212 KB | Output is correct |
12 | Correct | 0 ms | 212 KB | Output is correct |
13 | Correct | 0 ms | 212 KB | Output is correct |
14 | Correct | 0 ms | 212 KB | Output is correct |
15 | Correct | 1 ms | 212 KB | Output is correct |
16 | Correct | 1 ms | 212 KB | Output is correct |
17 | Correct | 1 ms | 212 KB | Output is correct |
18 | Correct | 0 ms | 212 KB | Output is correct |
19 | Correct | 0 ms | 212 KB | Output is correct |
20 | Correct | 1 ms | 212 KB | Output is correct |
21 | Correct | 0 ms | 212 KB | Output is correct |
22 | Correct | 0 ms | 212 KB | Output is correct |
23 | Correct | 0 ms | 212 KB | Output is correct |
24 | Correct | 0 ms | 212 KB | Output is correct |
25 | Correct | 0 ms | 320 KB | Output is correct |
26 | Correct | 1 ms | 212 KB | Output is correct |
27 | Correct | 0 ms | 320 KB | Output is correct |
28 | Correct | 1 ms | 340 KB | Output is correct |
29 | Correct | 1 ms | 340 KB | Output is correct |
30 | Correct | 1 ms | 340 KB | Output is correct |
31 | Correct | 1 ms | 324 KB | Output is correct |
32 | Correct | 1 ms | 340 KB | Output is correct |
33 | Correct | 1 ms | 340 KB | Output is correct |
34 | Correct | 1 ms | 324 KB | Output is correct |
35 | Correct | 1 ms | 340 KB | Output is correct |
36 | Correct | 1 ms | 316 KB | Output is correct |
37 | Correct | 1 ms | 340 KB | Output is correct |
38 | Correct | 1 ms | 340 KB | Output is correct |
39 | Correct | 1 ms | 340 KB | Output is correct |
40 | Correct | 1 ms | 340 KB | Output is correct |
41 | Correct | 3 ms | 1876 KB | Output is correct |
42 | Correct | 4 ms | 1816 KB | Output is correct |
43 | Correct | 9 ms | 1876 KB | Output is correct |
44 | Correct | 39 ms | 1688 KB | Output is correct |
45 | Correct | 62 ms | 1748 KB | Output is correct |
46 | Correct | 66 ms | 2208 KB | Output is correct |
47 | Correct | 5 ms | 1736 KB | Output is correct |
48 | Correct | 17 ms | 1736 KB | Output is correct |
49 | Correct | 28 ms | 1860 KB | Output is correct |
50 | Correct | 32 ms | 1876 KB | Output is correct |
51 | Correct | 3 ms | 1876 KB | Output is correct |
52 | Correct | 4 ms | 1876 KB | Output is correct |
53 | Correct | 3 ms | 1876 KB | Output is correct |
54 | Correct | 5 ms | 1876 KB | Output is correct |
55 | Correct | 56 ms | 1876 KB | Output is correct |
56 | Correct | 34 ms | 1884 KB | Output is correct |
57 | Correct | 34 ms | 1876 KB | Output is correct |
58 | Correct | 3 ms | 2132 KB | Output is correct |
59 | Correct | 3 ms | 2120 KB | Output is correct |
60 | Correct | 22 ms | 1736 KB | Output is correct |
61 | Correct | 22 ms | 1868 KB | Output is correct |
62 | Execution timed out | 4024 ms | 68080 KB | Time limit exceeded |
63 | Halted | 0 ms | 0 KB | - |