제출 #343786

#제출 시각아이디문제언어결과실행 시간메모리
343786IZhO_2021_I_want_SilverLongest beautiful sequence (IZhO17_subsequence)C++14
100 / 100
4078 ms3564 KiB
#pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx") #include <iostream> #include <algorithm> #include <vector> #include <cmath> #include <set> #include <map> #include <iomanip> #include <cassert> #include <stack> #include <queue> #include <deque> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp>- using namespace std; //using namespace __gnu_pbds; typedef long long ll; typedef pair <int, int> pii; typedef pair <ll, ll> pll; // template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; // order_of_key (k) : Number of items strictly smaller than k . // find_by_order(k) : K-th element in a set (counting from zero). #define sz(a) (int)a.size() #define all(a) a.begin(), a.end() #define pb push_back #define ppb pop_back #define mkp make_pair #define F first #define S second #define lb lower_bound #define ub upper_bound #define show(a) cerr << #a <<" -> "<< a <<" " #define nl cerr <<"\n" //#define int ll const int N = 2e6 + 5; const int oo = 1e9 + 5; int n, a[N], k[N], dp[N], pre[N], mx[N]; vector <int> vec; void solve() { cin >> n; for (int i = 1; i <= n; ++i) { cin >> a[i]; } for (int i = 1; i <= n; ++i) { cin >> k[i]; dp[i] = 1; mx[i] = 1; } int ans = 1, pos = 1; for (int i = 1; i <= n; ++i) { mx[i] = max(mx[i-1], dp[i]); if (__builtin_popcount(a[i]) < k[i]) { continue; } for (int j = i-1; j >= 1; --j) { if (__builtin_popcount(a[i] & a[j]) == k[i]) { if (dp[i] < dp[j] + 1) { dp[i] = dp[j] + 1; pre[i] = j; } if (ans < dp[i]) { ans = dp[i]; pos = i; } } if (dp[i] > mx[j]) { break; } } mx[i] = max(mx[i-1], dp[i]); } while (pre[pos]) { vec.pb(pos); pos = pre[pos]; } vec.pb(pos); reverse(all(vec)); cout << sz(vec) <<"\n"; for (int i = 0; i < sz(vec); ++i) { cout << vec[i] <<" "; } } main () { ios_base::sync_with_stdio(false); cin.tie(NULL); int tests = 1; //cin >> tests; while (tests --) { solve(); } return 0; } /* Just Chalish! 4 1 2 3 4 10 0 1 0 2 8 9 20 0 5 5 3 5 3 5 10 1 20 1 20 */

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

subsequence.cpp:88:8: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   88 |  main () {
      |        ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...