답안 #982612

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
982612	2024-05-14T13:37:39 Z	SmuggingSpun	Global Warming (CEOI18_glo)	C++14	55 / 100	51 ms	3420 KB

#include<bits/stdc++.h>
#define taskname "glo"
using namespace std;
typedef long long ll;
template<class T>void maximize(T& a, T b){
	if(a < b){
		a = b;
	}
}
const int lim = 2e5 + 5;
const int INF = 2e9 + 1;
int n, X, a[lim];
namespace sub12{
	void solve(){
		int ans = 0;
		for(int i = 1; i <= n; i++){
			for(int j = i; j <= n; j++){
				for(int d = -X; d <= X; d++){
					vector<int>t(n + 1), f(n + 1, INF);
					for(int k = 1; k <= n; k++){
						t[k] = a[k];
					}
					for(int k = i; k <= j; k++){
						t[k] += d;
					}
					f[0] = -INF;
					for(int k = 1; k <= n; k++){
						int low = 0, high = n - 1, p;
						while(low <= high){
							int mid = (low + high) >> 1;
							if(f[mid] < t[k]){
								low = (p = mid) + 1;
							}
							else{
								high = mid - 1;
							}
						}
						f[++p] = t[k];
						maximize(ans, p);
					}
				}
			}
		}	
		cout << ans;	
	}
}
namespace sub4{
	void solve(){
		vector<int>f(n + 1, INF);
		f[0] = -INF;
		int ans = 0;
		for(int k = 1; k <= n; k++){
			int low = 0, high = n - 1, p;
			while(low <= high){
				int mid = (low + high) >> 1;
				if(f[mid] < a[k]){
					low = (p = mid) + 1;
				}
				else{
					high = mid - 1;
				}
			}
			f[++p] = a[k];
			maximize(ans, p);
		}
		cout << ans;
	}
}
namespace sub6{
	int f[lim], p[lim];
	void solve(){
		fill(p, p + lim, INF);
		p[0] = -INF;
		for(int i = 1; i <= n; i++){
			int low = 0, high = n - 1, P;
			while(low <= high){
				int mid = (low + high) >> 1;
				if(p[mid] < a[i]){
					low = (P = mid) + 1;
				}
				else{
					high = mid - 1;
				}
			}
			p[++P] = a[i];
			f[i] = max(f[i - 1], P);
		}
		int ans = f[n];
		fill(p, p + lim, -INF);
		p[0] = INF;
		for(int i = n, pre = 0; i > 0; i--){
			int low = 0, high = n - 1, P;
			a[i] += X;
			while(low <= high){
				int mid = (low + high) >> 1;
				if(p[mid] > a[i]){
					low = (P = mid) + 1;
				}
				else{
					high = mid - 1;
				}
			}
			p[++P] = a[i];
			maximize(ans, (pre = max(pre, P)) + f[i - 1]);
		}
		cout << ans;
	}
}
namespace sub3{
	void solve(){
		int ans = 0;
		for(int i = n; i > 0; a[i--] += X){
			vector<int>f(n + 1, INF);
			f[0] = -INF;
			for(int k = 1; k <= n; k++){
				int low = 0, high = n - 1, p;
				while(low <= high){
					int mid = (low + high) >> 1;
					if(f[mid] < a[k]){
						low = (p = mid) + 1;
					}
					else{
						high = mid - 1;
					}
				}
				f[++p] = a[k];
				maximize(ans, p);
			}
		}
		cout << ans;
	}
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	cin >> n >> X;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	if(n <= 50){
		sub12::solve();
	}
	else if(n <= 1000){
		sub3::solve();
	}
	else if(X == 0){
		sub4::solve();
	}
	else if(X == 1000000000){
		sub6::solve();
	}
}

Compilation message

glo.cpp: In function 'int main()':
glo.cpp:136:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |   freopen(taskname".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
glo.cpp: In function 'void sub6::solve()':
glo.cpp:103:6: warning: 'P' may be used uninitialized in this function [-Wmaybe-uninitialized]
  103 |    p[++P] = a[i];
      |      ^~~
glo.cpp:85:6: warning: 'P' may be used uninitialized in this function [-Wmaybe-uninitialized]
   85 |    p[++P] = a[i];
      |      ^~~
glo.cpp: In function 'void sub3::solve()':
glo.cpp:126:12: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
  126 |     f[++p] = a[k];
glo.cpp: In function 'void sub12::solve()':
glo.cpp:38:14: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
   38 |       f[++p] = t[k];
glo.cpp: In function 'void sub4::solve()':
glo.cpp:63:11: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
   63 |    f[++p] = a[k];

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	1 ms	2468 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	1 ms	2392 KB	Output is correct
11	Correct	1 ms	2396 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	1 ms	2468 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	1 ms	2392 KB	Output is correct
11	Correct	1 ms	2396 KB	Output is correct
12	Correct	16 ms	2396 KB	Output is correct
13	Correct	1 ms	2396 KB	Output is correct
14	Correct	51 ms	2512 KB	Output is correct
15	Correct	26 ms	2648 KB	Output is correct
16	Correct	22 ms	2396 KB	Output is correct
17	Correct	1 ms	2396 KB	Output is correct
18	Correct	1 ms	2396 KB	Output is correct

Subtask #3
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	1 ms	2468 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	1 ms	2392 KB	Output is correct
11	Correct	1 ms	2396 KB	Output is correct
12	Correct	16 ms	2396 KB	Output is correct
13	Correct	1 ms	2396 KB	Output is correct
14	Correct	51 ms	2512 KB	Output is correct
15	Correct	26 ms	2648 KB	Output is correct
16	Correct	22 ms	2396 KB	Output is correct
17	Correct	1 ms	2396 KB	Output is correct
18	Correct	1 ms	2396 KB	Output is correct
19	Correct	18 ms	2396 KB	Output is correct
20	Correct	15 ms	2532 KB	Output is correct
21	Correct	14 ms	2396 KB	Output is correct
22	Correct	15 ms	2536 KB	Output is correct
23	Correct	16 ms	2396 KB	Output is correct
24	Correct	15 ms	2396 KB	Output is correct
25	Correct	15 ms	2396 KB	Output is correct
26	Correct	21 ms	2396 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	3416 KB	Output is correct
2	Correct	27 ms	3308 KB	Output is correct
3	Correct	26 ms	3280 KB	Output is correct
4	Correct	29 ms	3420 KB	Output is correct
5	Correct	19 ms	3420 KB	Output is correct

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	4 ms	2396 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #6
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	2652 KB	Output is correct
2	Correct	19 ms	2512 KB	Output is correct
3	Correct	40 ms	2788 KB	Output is correct
4	Correct	28 ms	2648 KB	Output is correct
5	Correct	16 ms	2648 KB	Output is correct
6	Correct	24 ms	2652 KB	Output is correct
7	Correct	26 ms	2768 KB	Output is correct
8	Correct	15 ms	2688 KB	Output is correct

Subtask #7
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	1 ms	2468 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	1 ms	2392 KB	Output is correct
11	Correct	1 ms	2396 KB	Output is correct
12	Correct	16 ms	2396 KB	Output is correct
13	Correct	1 ms	2396 KB	Output is correct
14	Correct	51 ms	2512 KB	Output is correct
15	Correct	26 ms	2648 KB	Output is correct
16	Correct	22 ms	2396 KB	Output is correct
17	Correct	1 ms	2396 KB	Output is correct
18	Correct	1 ms	2396 KB	Output is correct
19	Correct	18 ms	2396 KB	Output is correct
20	Correct	15 ms	2532 KB	Output is correct
21	Correct	14 ms	2396 KB	Output is correct
22	Correct	15 ms	2536 KB	Output is correct
23	Correct	16 ms	2396 KB	Output is correct
24	Correct	15 ms	2396 KB	Output is correct
25	Correct	15 ms	2396 KB	Output is correct
26	Correct	21 ms	2396 KB	Output is correct
27	Correct	27 ms	3416 KB	Output is correct
28	Correct	27 ms	3308 KB	Output is correct
29	Correct	26 ms	3280 KB	Output is correct
30	Correct	29 ms	3420 KB	Output is correct
31	Correct	19 ms	3420 KB	Output is correct
32	Incorrect	4 ms	2396 KB	Output isn't correct
33	Halted	0 ms	0 KB	-

답안 #982612

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 10.0 / 10.0

Subtask #3 13.0 / 13.0

Subtask #4 10.0 / 10.0

Subtask #5 0 / 20.0

Subtask #6 17.0 / 17.0

Subtask #7 0 / 25.0

Subtask #1
5.0 / 5.0

Subtask #2
10.0 / 10.0

Subtask #3
13.0 / 13.0

Subtask #4
10.0 / 10.0

Subtask #5
0 / 20.0

Subtask #6
17.0 / 17.0

Subtask #7
0 / 25.0