Submission #920109

#	Time	Username	Problem	Language	Result	Execution time	Memory
920109		Ghulam_Junaid	Global Warming (CEOI18_glo)	C++17	25 / 100	69 ms	4440 KiB

glo

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

const int inf = 1e9 + 7;

int main(){
    int n, x;
    cin >> n >> x;

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

    int dp[n + 1] = {0};
    for (int i = 1; i <= n; i ++)
        dp[i] = inf;

    int ans = 0;
    int pref[n] = {0};
    for (int i = 0; i < n; i ++){
        int ub = lower_bound(dp, dp + n + 1, a[i]) - dp;
        dp[ub] = a[i];
        ans = max(ans, ub);
        pref[i] = ub;
    }

    if (x == 0){
        cout << ans << endl;
        return 0;
    }

    int cpy[n];
    if (n <= 50 and x <= 50){
        for (int d = -x; d <= x; d++){
            for (int l = 0; l < n; l ++){
                for (int r = l; r < n; r ++){
                    for (int i = 0; i < n; i ++)
                        cpy[i] = a[i] + d * (l <= i and i <= r);

                    for (int i = 1; i <= n; i++)
                        dp[i] = inf;
                    dp[0] = -inf;

                    for (int i = 0; i < n; i ++){
                        int ub = lower_bound(dp, dp + n + 1, cpy[i]) - dp;
                        dp[ub] = cpy[i];
                        ans = max(ans, ub);
                    }
                }
            }
        }

        cout << ans << endl;
        return 0;
    }
    
    if (x < 6){
        for (int d = 0; d <= x; d ++){
            for (int i = 1; i <= n; i++)
                dp[i] = inf;
            dp[0] = -inf;

            for (int i = n - 1; i >= 0; i--){
                int ub = lower_bound(dp, dp + n + 1, -(a[i] + d)) - dp;
                dp[ub] = -(a[i] + d);
                ans = max(ans, pref[i] + ub);
            }
        }
        cout << ans << endl;
        return 0;
    }

    cout << 1 / 0 << endl;
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:73:15: warning: division by zero [-Wdiv-by-zero]
   73 |     cout << 1 / 0 << endl;
      |             ~~^~~

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