이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")
#define fi first
#define se second
#define ll long long
#define dl double long
using namespace std;
const int NN = 2e6 + 7;
const int N = 1e6 + 7;
const int M = 22;
const int mod = 998244353;
const ll inf = 1e18 + 7;
const dl rf = 1e-14;
const int B = sqrt(N);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n;
int a[N];
int k[N];
pair < int , int > dp[N];
pair < int , int > d[(1 << 10)][(1 << 10)][10];
void solve1()
{
cin >> n;
pair < int , int > ans = {0 , 0};
for( int i = 1; i <= n; i++ )cin >> a[i];
for( int i = 1; i <= n; i++ )cin >> k[i];
for( int i = 1; i <= n; i++ ){
dp[i] = {1 , 0};
int h1 = (a[i] >> 10);
int h2 = (a[i] & ((1 << 10) - 1));
for( int j = 0; j < (1 << 10); j++ ){
int f = __builtin_popcount((h2 & j));
if( k[i] - f >= 0 && k[i] - f <= 10 ){
dp[i] = max( make_pair(d[j][h1][k[i] - f].fi + 1 , d[j][h1][k[i] - f].se) , dp[i] );
}
}
for( int j = 0; j < (1 << 10); j++ ){
d[h2][j][(j & h1)] = max( d[h2][j][(j & h1)] , make_pair(dp[i].fi , i) );
}
ans = max( ans , {dp[i].fi , i} );
}
cout << ans.fi << "\n";
vector < int > res;
while( ans.se != 0 ){
res.push_back(ans.se);
ans.se = dp[ans.se].se;
}
assert( ans.fi == (int)res.size() );
reverse( res.begin() , res.end() );
for( auto x : res )cout << x << " ";
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
//freopen( "input.txt" , "r" , stdin );
//freopen( "output.txt" , "w" , stdout );
int cghf = 1;//cin >> cghf;
while( cghf-- ){
solve1();
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |