Submission #654178

#	Time	Username	Problem	Language	Result	Execution time	Memory
654178		ilia_rr	Financial Report (JOI21_financial)	C++14	26 / 100	45 ms	5840 KiB

Main

// بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيمِ
// Written by Ilia Rahbar

// #pragma GCC optimize ("O3,no-stack-protector,unroll-loops,fast-math")
// #pragma GCC target ("abm,bmi,bmi2,tbm,avx2")

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

#define int int64_t
#define ai(x) array <int, x>
#define F first 
#define S second

const int MOD = 1e9 + 7, N = 1e6 + 100;

int n, d, a[N], p, ok, m, ans, c;

int32_t main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> d;

    for (int i = 0; i < n; i++)
        cin >> a[i];

    if (n <= 20)
    {
        for (int i = (1 << (n-1)) - 1; i >= 0; i--)
        {
            p = n-1;

            ok = 1;

            for (int j = n-2; j >= 0; j--)
            {
                if (i >> j & 1)
                {
                    ok &= (p - j <= d);

                    p = j;
                }
            }

            if (!ok)
                continue;

            m = -1;
            
            c = 0;

            for (int j = 0; j < n - 1; j++)
            {
                if (i >> j & 1)
                {
                    c += (m < a[j]);

                    m = max(m, a[j]);
                }
            }

            ans = max(ans, c + (m < a[n-1]));
        }
    }
    
    else if (d == 1)
    {
        stack <int> s;

        for (int i = n-1; i >= 0; i--)
        {
            while (s.size() && a[s.top()] <= a[i])
                s.pop();

            s.push(i);

            ans = max(ans, int(s.size()));
        }
    }

    cout << ans;
}

• Subtask 1: 14 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 20
• Subtask 4: 12 / 12
• Subtask 5: 0 / 5
• Subtask 6: 0 / 35