Submission #380882

#	Time	Username	Problem	Language	Result	Execution time	Memory
380882		Killer2501	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	5828 ms	95960 KiB

subsequence

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define task "asd"
#define pll pair<ll, ll>
#define pii pair<pll, ll>
#define fi first
#define se second
using namespace std;
const ll mod = 1e9;
const ll N = (1<<10);
const int base = 313;
ll n, m, t, k, T, ans, siz, tong, a[N*N], b[N*N], d[N], c[N*N], dp[N+5][N+5][11];
string s, sa, sb;

vector<ll> adj[N], kq;


ll pw(ll k, ll n)
{
    ll total = 1;
    for(; n; n >>= 1)
    {
        if(n & 1)total = total * k % m;
        k = k * k % m;
    }
    return total;
}

void truyvet(int i)
{
    kq.pb(i);
    if(c[i] == 1)return;
    for(int j = i-1; j > 0; j --)
    {
        if(c[i] == c[j] + 1 && __builtin_popcount(a[i] & a[j]) == b[i])
        {
            truyvet(j);
            return;
        }
    }
}
void sol()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)cin >> a[i];
    for(int i = 1; i <= n; i ++)cin >> b[i];
    ll id = 0;
    for(int i = 1; i <= n; i ++)
    {
        c[i] = 1;
        pll x;
        x.fi = (a[i] >> 10);
        x.se = (a[i] & ((1<<10)-1));
        for(int j = 0; j < (1<<10); j ++)
        {
            k = __builtin_popcountll(j&x.fi);
            if(k > b[i] || b[i] - k > 10)continue;
            c[i] = max(c[i], dp[j][x.se][b[i]-k] + 1);
        }
        for(int j = 0; j < (1<<10); j ++)
        {
            k = __builtin_popcountll(j&x.se);
            dp[x.fi][j][k] = max(dp[x.fi][j][k], c[i]);
        }
        if(ans < c[i])
        {
            ans = c[i];
            id = i;
        }
    }
    cout << ans << '\n';
    truyvet(id);
    reverse(kq.begin(), kq.end());
    for(ll x : kq)cout << x <<" ";
}
int main()
{
    if(fopen(task".INP", "r"))
    {
       freopen(task".INP", "r", stdin);
       freopen(task".OUT", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int ntest = 1;
    //cin >> ntest;
    while(ntest -- > 0)
    sol();
}
/*
5
5 3 5 3 5
10 1 20 1 20
https://codeforces.com/contest/791/problem/E

*/

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:81:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   81 |        freopen(task".INP", "r", stdin);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
subsequence.cpp:82:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   82 |        freopen(task".OUT", "w", stdout);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 60 / 60