oj.uz

Submission #812016

# Submission time Handle Problem Language Result Execution time Memory
812016 2023-08-07T06:47:58 Z vjudge1 Financial Report (JOI21_financial) C++14
45 / 100
 1394 ms 36156 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std ;
const int N = (1 << 19) ;
int n, d, cnt, a[N + 1], dp[N + 1], mx[2 * N + 1] ;
set<int> s ;
map<int, int> mp ;
void update(int l, int r, int ind, int num, int v)
{
    if(l > ind || r < ind)
        return ;
    if(l == r)
    {
        mx[v] = num ;
        return ;
    }
    int mid = (l + r) >> 1 ;
    update(l, mid, ind, num, v * 2) ;
    update(mid + 1, r, ind, num, v * 2 + 1) ;
    mx[v] = max(mx[v * 2], mx[v * 2 + 1]) ;
}
int get_max(int l, int r,int l1, int r1, int v)
{
    if(l > r1 || r < l1)
        return 0 ;
    if(l1 <= l && r <= r1)
        return mx[v] ;
    int mid = (l + r) >> 1 ;
    return max(get_max(l, mid, l1, r1, v * 2), get_max(mid + 1, r, l1, r1, v * 2 + 1)) ;
}
signed main()
{
    ios_base::sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cout.tie( 0 ) ;
    cin >> n >> d ;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> a[i] ;
        s.insert(a[i]) ;
    }
    for(int i : s)
    {
        cnt++ ;
        mp[i] = cnt ;
    }
    for(int i = 1 ; i <= n ; i++)
        a[i] = mp[a[i]] ;
    if(n <= 400)
    {
        int ans = 0 ;
        for(int i = n ; i >= 1 ; i--)
        {
            int mx = 0 ;
            for(int j = i + 1 ; j <= n ; j++)
                if(a[j] > a[i])
                {
                    bool flag = 0 ;
                    vector<int> v ;
                    v.push_back(i) ;
                    for(int q = i + 1 ; q <= j ; q++)
                        if(a[q] < a[j])
                        {
                            if(q - v.back() > d)
                                flag = 1 ;
                            v.push_back(q) ;
                        }
                    if(j - v.back() > d)
                        flag = 1 ;
                    if(!flag)
                        mx = max(mx, dp[j]) ;
                }
            dp[i] = mx + 1 ;
            ans = max(ans, dp[i]) ;
        }
//        for(int i = 1 ; i <=n;i++)
//        {
//        }
        cout << ans ;
        return 0 ;
    }
    if(n <= 20)
    {
        int ans = 0 ;
        for(int i = 0 ; i < (1 << n) ; i++)
        {
            int now = 0, mx = -1, ls = 1e9 ;
            for(int j = 0 ; j < n ; j++)
                if(j - ls <= d && ((1 << j) & i))
                {
                    ls = j ;
                    if(mx < a[j + 1])
                        now++ ;
                    mx = max(mx, a[j + 1]) ;
                }
            ans = max(ans, now) ;
        }
        cout << ans ;
        return 0 ;
    }
    if(d == 1)
    {
        int ans = 0 ;
        for(int i = 1 ; i <= n ; i++)
            update(1, N, i, a[i], 1) ;
        for(int i = n ; i >= 1 ; i--)
        {
            int l = i, r = n + 1 ;
            while(l + 1 < r)
            {
                int mid = (l + r) >> 1 ;
                if(get_max(1, N, i, mid, 1) > a[i])
                    r = mid ;
                else
                    l = mid ;
            }
            dp[i] = dp[r] + 1 ;
            ans = max(ans, dp[i]) ;
        }
        cout << ans ;
        return 0 ;
    }
    if(d == n)
    {
        int ans = 0 ;
        for(int i = 1 ; i <= n ; i++)
        {
            int num = get_max(1, N, 1, a[i] - 1, 1) ;
            ans = max(ans, num + 1) ;
            update(1, N, a[i], num + 1, 1) ;
        }
        cout << ans ;
        return 0 ;
    }
    return 0 ;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 0 ms 328 KB Output is correct
23 Correct 0 ms 324 KB Output is correct
24 Correct 0 ms 344 KB Output is correct
25 Correct 0 ms 340 KB Output is correct
26 Correct 0 ms 348 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 0 ms 328 KB Output is correct
23 Correct 0 ms 324 KB Output is correct
24 Correct 0 ms 344 KB Output is correct
25 Correct 0 ms 340 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 23 ms 340 KB Output is correct
28 Correct 23 ms 340 KB Output is correct
29 Correct 20 ms 340 KB Output is correct
30 Correct 21 ms 344 KB Output is correct
31 Correct 10 ms 340 KB Output is correct
32 Correct 24 ms 340 KB Output is correct
33 Correct 27 ms 364 KB Output is correct
34 Correct 27 ms 368 KB Output is correct
35 Correct 30 ms 340 KB Output is correct
36 Correct 28 ms 340 KB Output is correct
37 Correct 38 ms 340 KB Output is correct
38 Correct 43 ms 348 KB Output is correct
39 Correct 27 ms 324 KB Output is correct
40 Correct 21 ms 368 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 0 ms 328 KB Output is correct
23 Correct 0 ms 324 KB Output is correct
24 Correct 0 ms 344 KB Output is correct
25 Correct 0 ms 340 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 23 ms 340 KB Output is correct
28 Correct 23 ms 340 KB Output is correct
29 Correct 20 ms 340 KB Output is correct
30 Correct 21 ms 344 KB Output is correct
31 Correct 10 ms 340 KB Output is correct
32 Correct 24 ms 340 KB Output is correct
33 Correct 27 ms 364 KB Output is correct
34 Correct 27 ms 368 KB Output is correct
35 Correct 30 ms 340 KB Output is correct
36 Correct 28 ms 340 KB Output is correct
37 Correct 38 ms 340 KB Output is correct
38 Correct 43 ms 348 KB Output is correct
39 Correct 27 ms 324 KB Output is correct
40 Correct 21 ms 368 KB Output is correct
41 Correct 16 ms 696 KB Output is correct
42 Incorrect 3 ms 980 KB Output isn't correct
43 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1152 ms 7908 KB Output is correct
2 Correct 1066 ms 7632 KB Output is correct
3 Correct 1054 ms 7948 KB Output is correct
4 Correct 1280 ms 31936 KB Output is correct
5 Correct 1216 ms 36048 KB Output is correct
6 Correct 1319 ms 36044 KB Output is correct
7 Correct 1231 ms 35804 KB Output is correct
8 Correct 1296 ms 35968 KB Output is correct
9 Correct 1131 ms 36156 KB Output is correct
10 Correct 1284 ms 36084 KB Output is correct
11 Correct 1202 ms 36044 KB Output is correct
12 Correct 1256 ms 36108 KB Output is correct
13 Correct 1291 ms 36156 KB Output is correct
14 Correct 1394 ms 36016 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 4652 KB Output is correct
2 Correct 100 ms 4288 KB Output is correct
3 Correct 141 ms 4808 KB Output is correct
4 Correct 432 ms 34864 KB Output is correct
5 Correct 498 ms 34872 KB Output is correct
6 Correct 414 ms 34912 KB Output is correct
7 Correct 216 ms 34888 KB Output is correct
8 Correct 232 ms 34908 KB Output is correct
9 Correct 232 ms 34708 KB Output is correct
10 Correct 291 ms 34792 KB Output is correct
11 Correct 446 ms 34888 KB Output is correct
12 Correct 325 ms 34944 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 0 ms 328 KB Output is correct
23 Correct 0 ms 324 KB Output is correct
24 Correct 0 ms 344 KB Output is correct
25 Correct 0 ms 340 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 23 ms 340 KB Output is correct
28 Correct 23 ms 340 KB Output is correct
29 Correct 20 ms 340 KB Output is correct
30 Correct 21 ms 344 KB Output is correct
31 Correct 10 ms 340 KB Output is correct
32 Correct 24 ms 340 KB Output is correct
33 Correct 27 ms 364 KB Output is correct
34 Correct 27 ms 368 KB Output is correct
35 Correct 30 ms 340 KB Output is correct
36 Correct 28 ms 340 KB Output is correct
37 Correct 38 ms 340 KB Output is correct
38 Correct 43 ms 348 KB Output is correct
39 Correct 27 ms 324 KB Output is correct
40 Correct 21 ms 368 KB Output is correct
41 Correct 16 ms 696 KB Output is correct
42 Incorrect 3 ms 980 KB Output isn't correct
43 Halted 0 ms 0 KB -