제출 #1369119

#제출 시각아이디문제언어결과실행 시간메모리
1369119mhn_neekLongest beautiful sequence (IZhO17_subsequence)C++20
100 / 100
1306 ms94128 KiB
//In the name of God
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef long double ld;
typedef pair<lli,lli> pii;
typedef pair<pii,pii> piiii;
typedef vector<lli> ve;
typedef vector<pii> vp;
const lli N=3e5+100;
const lli mod=1e9+7;//998244353;//1e9+9
const lli INF=1e18;
lli power(lli x,lli y){lli res = 1;x = x % mod;while(y>0){if( y & 1 ){res = (res * x) % mod;}y = y >> 1;x = (x * x)%mod;}return res;}
lli modinv(lli x){return power(x,mod-2);}
lli divide(lli x,lli y){return ((x%mod) * modinv(y))%mod;}
#define all(v) v.begin(),v.end()
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define migmig ios_base::sync_with_stdio(false),cout.tie(0), cin.tie(0);
#define read freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define minheap priority_queue<pair<lli,pii>, std::vector<pair<lli,pii>>, std::greater<pair<lli,pii>>>
#define set_preci(x) cout << fixed << setprecision(x);
#define debug(x) cerr << (#x) << " " << (x) << endl
#define MP make_pair
#define PB push_back
#define fi first
#define se second
#define SUM(v) accumulate(v.begin(),v.end(), 0LL)
#define FOR(x,n) for(lli x = 0; x < n; x++)
#define FORS(x,n) for(lli x = 1; x <= n; x++)
#define TEST int TQPWIEJR; cin>>TQPWIEJR;while(TQPWIEJR--)
#define BN(l,a) while(l){a.PB(l%2);l/=2;}
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define sep " "
#define SZ(X) (lli)X.size()
lli tmp;
int bv[1024][1024][11];
int bi[1024][1024][11];
lli a[N], k[N], dp[N], p[N];

int main(){
    migmig;
    
    lli n;
    cin >> n;
    
    FORS(i, n) cin >> a[i];
    FORS(i, n) cin >> k[i];
    
    memset(bi, -1, sizeof(bi));
    
    lli mx = 0, idx = -1;
    
    FORS(i, n) {
        dp[i] = 1;
        p[i] = -1;
        
        int y1 = a[i] >> 10;
        int y2 = a[i] & 1023;
        
        FOR(x1, 1024) {
            int c = k[i] - __builtin_popcount(x1 & y1);
            if(c >= 0 && c <= 10) {
                if(bv[x1][y2][c] + 1 > dp[i]) {
                    dp[i] = bv[x1][y2][c] + 1;
                    p[i] = bi[x1][y2][c];
                }
            }
        }
        
        if(dp[i] > mx) {
            mx = dp[i];
            idx = i;
        }
        
        FOR(y, 1024) {
            int c = __builtin_popcount(y2 & y);
            if(dp[i] > bv[y1][y][c]) {
                bv[y1][y][c] = dp[i];
                bi[y1][y][c] = i;
            }
        }
    }
    
    ve ans;
    while(idx != -1) {
        ans.PB(idx);
        idx = p[idx];
    }
    
    reverse(all(ans));
    
    cout << mx << endl;
    FOR(i, SZ(ans)) {
        cout << ans[i] << sep;
    }
    cout << endl;
 
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…