Submission #736927

#	Time	Username	Problem	Language	Result	Execution time	Memory
736927		sleepntsheep	Global Warming (CEOI18_glo)	C++17	100 / 100	73 ms	6112 KiB

glo

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

using i8 = char;
using i16 = short;
using i32 = int;
using i64 = long long;
using u8 = unsigned char;
using u16 = unsigned short;
using u32 = unsigned int;
using u64 = unsigned long long;

int main()
{
    u8 Q;
    //scanf("%hhd", &Q);
    Q = 1;
    for (i32 n, k; Q--;)
    {
        constexpr i32 N = 200086;
        int t[N];
        scanf("%d%d", &n, &k);
        for (i32 i = 1; i <= n; ++i) scanf("%d", &t[i]);

        {
            int pf[N], sf[N];
            if (n <= 10)
            {
                i32 ans = 0;
                for (int i = 1; i <= n; ++i)
                    for (int j = i + 1; j <= n; ++j)
                        for (int x = -k; x <= k; ++x)
                        {
                            vector<int> blis;
                            for (int l = 1; l <= n; ++l)
                            {
                                auto u = (i <= l && l <= j ? t[l] + x : t[l]);
                                auto it = lower_bound(blis.begin(), blis.end(), u);
                                if (it == blis.end()) blis.push_back(u);
                                else *it = u;
                            }
                            ans = max(ans, (i32)blis.size());
                        }
                printf("%d\n", ans);
                continue;
            }

            {
                vector<i32> lis;
                for (i32 i = 1; i <= n; ++i)
                {
                    auto it = lower_bound(lis.begin(), lis.end(), t[i]);
                    if (it == lis.end()) lis.push_back(t[i]);
                    else *it = t[i];
                    pf[i] = lis.size();
                }
                lis.clear();
                for (i32 i = n; i >= 1; --i)
                {
                    auto it = lower_bound(lis.begin(), lis.end(), -t[i]);
                    if (it == lis.end()) lis.push_back(-t[i]);
                    else *it = -t[i];
                    sf[i] = lis.size();
                }
            }

            if (k == 0) 
            {
                printf("%d\n", pf[n]);
                continue;
            }
            if (k == 1000000000)
            {
                i32 ans = 0;
                for (i32 i = 1; i < n; ++i) ans = max(ans, pf[i] + sf[i+1]);
                printf("%d\n", ans);
                continue;
            }

            if (n <= 10000)
            {
                i32 ans = pf[n];
                for (int i = 1; i <= n; ++i)
                {
                    vector<int> blis;
                    for (int l = 1; l <= n; ++l)
                    {
                        auto u = l <= i ? t[l] : t[l] + k;
                        auto it = lower_bound(blis.begin(), blis.end(), u);
                        if (it == blis.end()) blis.push_back(u); else *it = u;
                    }
                    ans = max(ans, (i32)blis.size());
                }
                printf("%d\n", ans);
                continue;
            }

            {
                i32 ans = pf[n];
                vector<int> lis(n, INT_MAX), lds(n, INT_MAX);
                for (i32 i = 1; i <= n; ++i)
                {
                    pf[i] = lower_bound(lis.begin(), lis.end(), t[i] + k) - lis.begin();
                    *lower_bound(lis.begin(), lis.end(), t[i]) = t[i];
                }
                for (i32 i = n; i >= 1; --i)
                {
                    auto it = lower_bound(lds.begin(), lds.end(), -t[i]-k);
                    *it = -t[i]-k;
                    ans = max(ans, 1 + pf[i] + (i32)(it - lds.begin()));
                }
                printf("%d\n", ans);
            }

        }
    }
    return 0;
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:22:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         scanf("%d%d", &n, &k);
      |         ~~~~~^~~~~~~~~~~~~~~~
glo.cpp:23:43: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         for (i32 i = 1; i <= n; ++i) scanf("%d", &t[i]);
      |                                      ~~~~~^~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 25 / 25