답안 #982609

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
982609	2024-05-14T13:34:15 Z	SmuggingSpun	Global Warming (CEOI18_glo)	C++14	42 / 100	51 ms	4628 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 sub3567{
	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;
	}
}
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(X == 0){
		sub4::solve();
	}
	else{
		sub3567::solve();
	}
}

Compilation message

glo.cpp: In function 'int main()':
glo.cpp:112:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |   freopen(taskname".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
glo.cpp: In function 'void sub3567::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 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	2392 KB	Output is correct
2	Correct	1 ms	2608 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	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2392 KB	Output is correct
8	Correct	1 ms	2392 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	1 ms	2396 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	2392 KB	Output is correct
2	Correct	1 ms	2608 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	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2392 KB	Output is correct
8	Correct	1 ms	2392 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	1 ms	2396 KB	Output is correct
11	Correct	1 ms	2396 KB	Output is correct
12	Correct	15 ms	2392 KB	Output is correct
13	Correct	1 ms	2396 KB	Output is correct
14	Correct	51 ms	2648 KB	Output is correct
15	Correct	24 ms	2648 KB	Output is correct
16	Correct	20 ms	2508 KB	Output is correct
17	Correct	1 ms	2396 KB	Output is correct
18	Correct	1 ms	2396 KB	Output is correct

Subtask #3
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2392 KB	Output is correct
2	Correct	1 ms	2608 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	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2392 KB	Output is correct
8	Correct	1 ms	2392 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	1 ms	2396 KB	Output is correct
11	Correct	1 ms	2396 KB	Output is correct
12	Correct	15 ms	2392 KB	Output is correct
13	Correct	1 ms	2396 KB	Output is correct
14	Correct	51 ms	2648 KB	Output is correct
15	Correct	24 ms	2648 KB	Output is correct
16	Correct	20 ms	2508 KB	Output is correct
17	Correct	1 ms	2396 KB	Output is correct
18	Correct	1 ms	2396 KB	Output is correct
19	Incorrect	1 ms	2652 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 20.0

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

Subtask #6
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	2760 KB	Output is correct
2	Correct	20 ms	3420 KB	Output is correct
3	Correct	40 ms	4540 KB	Output is correct
4	Correct	28 ms	3928 KB	Output is correct
5	Correct	18 ms	3264 KB	Output is correct
6	Correct	26 ms	4060 KB	Output is correct
7	Correct	28 ms	4628 KB	Output is correct
8	Correct	16 ms	3420 KB	Output is correct

Subtask #7
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2392 KB	Output is correct
2	Correct	1 ms	2608 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	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2392 KB	Output is correct
8	Correct	1 ms	2392 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	1 ms	2396 KB	Output is correct
11	Correct	1 ms	2396 KB	Output is correct
12	Correct	15 ms	2392 KB	Output is correct
13	Correct	1 ms	2396 KB	Output is correct
14	Correct	51 ms	2648 KB	Output is correct
15	Correct	24 ms	2648 KB	Output is correct
16	Correct	20 ms	2508 KB	Output is correct
17	Correct	1 ms	2396 KB	Output is correct
18	Correct	1 ms	2396 KB	Output is correct
19	Incorrect	1 ms	2652 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

답안 #982609

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 10.0 / 10.0

Subtask #3 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
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