제출 #854167

#제출 시각아이디문제언어결과실행 시간메모리
854167anhphantGlobal Warming (CEOI18_glo)C++14
45 / 100
2060 ms7768 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll N, X, A[500007]; void initialize() { ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen("FILE.INP", "r")) { freopen("FILE.INP", "r", stdin); freopen("FILE.OUT", "w", stdout); } cin >> N >> X; for(int i = 1; i <= N; ++i) cin >> A[i]; } namespace subtask1 { ll LIS(vector<ll> v) { //for(int id = 1; id <= N; ++id) cerr << v[id] << " "; cerr << endl; ll ans = 0; for(ll mask = 1; mask < (1 << N); ++mask) { //cerr << "mask = " << mask << endl; ll last_value = -1e12; bool flag = 1; for(ll i = 0; i < N; ++i) { if (!(mask & (1 << i))) continue; if (last_value >= v[i + 1]) { flag = 0; break; } last_value = v[i + 1]; } if (flag) ans = max(ans, ll(__builtin_popcountll(mask))); } return ans; } void solve() { vector<ll> arr(N + 7, 0LL); for(int i = 1; i <= N; ++i) arr[i] = A[i]; ll res = 0; for(ll x = -X; x <= X; ++x) { //cerr << "x = " << x << endl; for(int i = 1; i <= N; ++i) { vector<ll> v = arr; for(int j = i; j <= N; ++j) { v[j] += x; res = max(res, LIS(v)); //cerr << i << " " << j << " " << LIS(v) << endl; } } } cout << res << endl; } void process() { solve(); } } namespace subtask2 { ll LIS(vector<ll> v) { vector<ll> bslen(N + 1, 0LL); for(int i = 1; i <= N; ++i) bslen[i] = 1e18; ll ans = 0; for(ll i = 1; i <= N; ++i) { ll k = lower_bound(bslen.begin(), bslen.end(), v[i]) - bslen.begin() - 1; ans = max(ans, k + 1); bslen[k + 1] = min(bslen[k + 1], v[i]); } return ans; } void solve() { vector<ll> arr(N + 7, 0LL); for(int i = 1; i <= N; ++i) arr[i] = A[i]; ll res = 0; for(ll x = -X; x <= X; ++x) { //cerr << "x = " << x << endl; for(int i = 1; i <= N; ++i) { vector<ll> v = arr; for(int j = i; j <= N; ++j) { v[j] += x; res = max(res, LIS(v)); //cerr << i << " " << j << " " << LIS(v) << endl; } } } cout << res << endl; } void process() { solve(); } } namespace subtask3 { ll LIS(vector<ll> v, ll x) { vector<ll> type1(N + 1, 0LL), type2(N + 1, 0LL), type3(N + 1, 0LL); for(int i = 1; i <= N; ++i) { type1[i] = type2[i] = type3[i] = 1e18; } int ans = 0; for(ll i = 1; i <= N; ++i) { int DP1 = lower_bound(type1.begin(), type1.end(), A[i]) - type1.begin() - 1; int DP2 = lower_bound(type2.begin(), type2.end(), A[i]) - type2.begin() - 1; DP2 = max(DP2, int(lower_bound(type1.begin(), type1.end(), A[i] + x) - type1.begin() - 1)); int DP3 = lower_bound(type3.begin(), type3.end(), A[i]) - type3.begin() - 1; DP3 = max(DP2, int(lower_bound(type2.begin(), type2.end(), A[i] - x) - type2.begin() - 1)); ans = max({ans, DP1 + 1, DP2 + 1, DP3 + 1}); DP1++; DP2++; DP3++; type1[DP1] = min(type1[DP1], A[i]); type2[DP2] = min(type2[DP2], A[i]); type3[DP3] = min(type3[DP3], A[i]); } return ans; } void solve() { vector<ll> arr(N + 7, 0LL); for(int i = 1; i <= N; ++i) arr[i] = A[i]; ll res = LIS(arr, 0); for(int i = 1; i <= N; ++i) { for(int j = i + 1; j <= N; ++j) { res = max(res, LIS(arr, A[i] - A[j])); res = max(res, LIS(arr, A[j] - A[i])); } } cout << res << endl; } void process() { solve(); } } namespace subtask4 { ll LIS(vector<ll> v) { vector<ll> bslen(N + 1, 0LL); for(int i = 1; i <= N; ++i) bslen[i] = 1e18; ll ans = 0; for(ll i = 1; i <= N; ++i) { ll k = lower_bound(bslen.begin(), bslen.end(), v[i]) - bslen.begin() - 1; ans = max(ans, k + 1); bslen[k + 1] = min(bslen[k + 1], v[i]); } return ans; } void solve() { vector<ll> arr(N + 7, 0LL); for(int i = 1; i <= N; ++i) arr[i] = A[i]; cout << LIS(arr); } void process() { solve(); } } namespace subtask5 { ll LIS(vector<ll> v, ll x) { vector<ll> type1(N + 1, 0LL), type2(N + 1, 0LL), type3(N + 1, 0LL); for(int i = 1; i <= N; ++i) { type1[i] = type2[i] = type3[i] = 1e18; } int ans = 0; for(ll i = 1; i <= N; ++i) { int DP1 = lower_bound(type1.begin(), type1.end(), A[i]) - type1.begin() - 1; int DP2 = lower_bound(type2.begin(), type2.end(), A[i]) - type2.begin() - 1; DP2 = max(DP2, int(lower_bound(type1.begin(), type1.end(), A[i] + x) - type1.begin() - 1)); int DP3 = lower_bound(type3.begin(), type3.end(), A[i]) - type3.begin() - 1; DP3 = max(DP2, int(lower_bound(type2.begin(), type2.end(), A[i] - x) - type2.begin() - 1)); ans = max({ans, DP1 + 1, DP2 + 1, DP3 + 1}); DP1++; DP2++; DP3++; type1[DP1] = min(type1[DP1], A[i]); type2[DP2] = min(type2[DP2], A[i]); type3[DP3] = min(type3[DP3], A[i]); } return ans; } void solve() { vector<ll> arr(N + 7, 0LL); for(int i = 1; i <= N; ++i) arr[i] = A[i]; ll res = 0; for(ll x = -X; x <= X; ++x) { res = max(res, LIS(arr, x)); } cout << res << endl; } void process() { solve(); } } int main() { initialize(); if (N <= 50) subtask2 :: process(); else if (X == 0) subtask4 :: process(); else if (N <= 1000) subtask3 :: process(); else subtask5 :: process(); }

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

glo.cpp: In function 'void initialize()':
glo.cpp:11:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |         freopen("FILE.INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
glo.cpp:12:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |         freopen("FILE.OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#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...