Submission #38262

#	Time	Username	Problem	Language	Result	Execution time	Memory
38262		mirbek01	Longest beautiful sequence (IZhO17_subsequence)	C++14	23 / 100	6000 ms	3576 KiB

subsequence

# include <bits/stdc++.h>

# define pb push_back
# define fr first
# define sc second
# define mk make_pair

using namespace std;

const long long linf = 1e18 + 7;
const int inf = 1e9 + 7;
const int N = 1e5 + 5;

typedef long long ll;

int n, a[N], k[N], dp[N], ot[N];
vector <int> ans;

int main(){
      cin >> n;

      for(int i = 1; i <= n; i ++){
            cin >> a[i];
            dp[i] = 1;
            ot[i] = i;
      }

      for(int i = 1; i <= n; i ++)
            cin >> k[i];

      int pos = 0, mx = -1;

      for(int i = 1; i <= n; i ++)
      {
            for(int j = i - 1; j >= 1; j --)
            {
                  int bit = __builtin_popcount(a[i] & a[j]);
                  if(bit == k[i])
                  {
                        if(dp[i] <= dp[j])
                        {
                              dp[i] = dp[j] + 1;
                              ot[i] = j;
                        }
                  }
            }

            if(mx < dp[i])
            {
                  mx = dp[i];
                  pos = i;
            }
      }

      mx = pos;

      while(1)
      {
            ans.pb(pos);
            pos = ot[pos];
            if(ans.size() >= dp[mx]) break;
      }

      cout << ans.size() << endl;
      reverse(ans.begin(), ans.end());
      for(int i : ans)
            cout << i << " ";
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:61:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(ans.size() >= dp[mx]) break;
                           ^

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