제출 #322412

#제출 시각아이디문제언어결과실행 시간메모리
322412Karen124Global Warming (CEOI18_glo)C++14
38 / 100
2086 ms2164 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long int #define F first #define S second #define pb push_back const ll N = 2e5 + 10; const ll LOG = 50; const ll MOD = 1e9 + 7; const ll INF = 1e9 + 10; int n, X, a[N], b[N], dp[2][N], ans, pd[2][N]; int LIS(int l, int r, int add){ int len = 0, p = 0, cn = 0; for (int i = 0; i <= n + 5; i++){ b[i] = 0; } for (int i = 1; i <= n; i++){ p = lower_bound(b, b + len, a[i] + (l <= i && i <= r) * add) - b; b[p] = a[i] + (l <= i && i <= r) * add; len = max(len, p + 1); } if (l == 0 && r == 0){ cout << len << '\n'; exit(0); } return len; } int main() { cin >> n >> X; for (int i = 1; i <= n; i++){ cin >> a[i]; } if (X == 0) {LIS(0, 0, 0);} else if (n <= 50 && X <= 50){ for (int l = 1; l <= n; l++){ for (int r = l; r <= n; r ++){ for (int i = -X; i <= X; i++){ ans = max(ans, LIS(l, r, i)); } } } cout << ans << '\n'; } else { for (int i = 1; i <= n; i++){ dp[0][i] = dp[1][i] = 1; dp[0][i] = max(dp[0][i], pd[0][i] + 1); for (int j = 0; j <= n + 5; j++) b[j] = 0; int len = 0, p = 0; for (int j = i; j >= 1; j--){ p = lower_bound(b, b + len, -(a[j] + X)) - b; b[p] = -(a[j] + X); len = max(len, p + 1); if (j) dp[1][i] = max(dp[1][i], pd[1][j] + p + 1); else dp[1][i] = max(dp[1][i], len); } for (int j = i + 1; j <= n; j++){ if (a[i] < a[j]) pd[0][j] = max(dp[0][i], pd[0][j]); if (a[i] < a[j] + X) pd[1][j] = max(dp[0][i], pd[1][j]); } ans = max({ans, dp[0][i], dp[1][i]}); } cout << ans << '\n'; } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

glo.cpp: In function 'int LIS(int, int, int)':
glo.cpp:16:25: warning: unused variable 'cn' [-Wunused-variable]
   16 |     int len = 0, p = 0, cn = 0;
      |                         ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...