| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1257243 | dosts | Longest beautiful sequence (IZhO17_subsequence) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define alperen_t int32_t
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 998244353, inf = 1e18;
const int N = 5e3+10;
const int lim = (1<<10);
pii tut[lim][lim][11];//solu böyle sağı şuna bu uzaklıkta
bool chmax(pii& p1,pii p2) {
if (p2.ff > p1.ff) p1 = p2;
else if (p2.ss < p1.ss) p1 = p2;
return (p1 == p2);
}
void solve() {
int n;
cin >> n;
vi a(n+1);
for (int i=1;i<=n;i++) cin >> a[i];
for (int i = 0;i<lim;i++) for (int j = 0;j<lim;j++) for (int k = 0;k<=10;k++) tut[i][j][k] ={-inf,inf};
vector<pii> dp(n+1);
for (int i=1;i<=n;i++) dp[i] = {1,i};
for (int i=1;i<=n;i++) {
int k;
cin >> k;
int sol = a[i] >> 10;
int sag = a[i]&1023;
for (int j = 0;j<lim;j++){
int ort = __builtin_popcountll(j&sol);
int rem = k-ort;
if (rem < 0) continue;
chmax(dp[i],{tut[j][sag][rem].ff+1,tut[j][sag][rem].ss});
}
for (int j = 0;j<lim;j++) {
int ortak = __builtin_popcountll(sag&j);
chmax(tut[sol][j][ortak],{dp[i].ff,i});
}
}
vi lmao;
auto mx = max_element(1+all(dp));
int ptr = mx-dp.begin();
vi v;
while (1) {
v.push_back(ptr);
if (dp[ptr].ff == 1) break;
ptr = dp[ptr].ss;
}
reverse(all(v));
cout << big(v) << '\n';
for (auto it : v) cout << it << ' ';
cout << '\n';
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef Dodi
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int t = 1;
//cin >> t;
while (t --> 0) solve();
#ifdef Dodi
cerr << "TIME TAKEN: " << (double)clock()/(double)CLOCKS_PER_SEC << "seconds!\n";
#endif
}ö