Submission #495563

#	Time	Username	Problem	Language	Result	Execution time	Memory
495563		aris12345678	Global Warming (CEOI18_glo)	C++14	100 / 100	72 ms	5372 KiB

glo

#include <bits/stdc++.h>
using namespace std;
 
const int mxN = 200005;
int t[mxN], dp1[mxN], pref[mxN], dp2[mxN];
 
int main() {
    int n, x;
    scanf("%d %d", &n, &x);
    for(int i = 0; i < n; i++)
        scanf("%d", &t[i]);
    fill(dp1, dp1+n, INT_MAX);
    int ans = 0;
    for(int i = 0; i < n; i++) {
        int pos = lower_bound(dp1, dp1+n, t[i])-dp1;
        dp1[pos] = t[i];
        pref[i] = pos+1;
        ans = max(ans, pref[i]);
    }
    fill(dp2, dp2+n, INT_MAX);
    for(int i = n-1; i >= 0; i--) {
        int res = lower_bound(dp2, dp2+n, -t[i]+x)-dp2;
        ans = max(ans, pref[i]+res);
        int pos = lower_bound(dp2, dp2+n, -t[i])-dp2;
        dp2[pos] = -t[i];
    }
    printf("%d\n", ans);
    return 0;
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:9:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |     scanf("%d %d", &n, &x);
      |     ~~~~~^~~~~~~~~~~~~~~~~
glo.cpp:11:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |         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