제출 #167202

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
167202		Nordway	Longest beautiful sequence (IZhO17_subsequence)	C++14	7 / 100	6046 ms	1444 KiB

subsequence

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define sz(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define nl "\n"

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
typedef pair<ll,ll> pll;

const int N = 1e3 + 11;
const int inf = 1e9;
const ll INF = 1e18;
const int mod = 1e9 + 7;

int dp[N][N], p[N][N], a[N], k[N];

int main(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
      cin >> a[i];
    }
    for(int i = 1; i <= n; i++){
      cin >> k[i];
      dp[1][i] = 1;
    }
    int len = n;
    int ind = n;
    for(int l = 2; l <= n; l++){
      int ok = 0;
      for(int i = l; i <= n; i++){
        for(int j = 1; j < i; j++){
          if(__builtin_popcount((a[i] & a[j])) == k[i]){
            if(dp[l - 1][j]){
              dp[l][i] = 1;
              p[l][i] = j;
            }
          }
        }
        ok |= dp[l][i];
       // cout << l << " " << i << " " << dp[l][i] << "\n";
        if(dp[l][i]){
          ind = i;
        }
      }
      if(!ok){
        len = l - 1;
        break;
      }
    }
    vector <int> ans;
    while(len > 0){
      ans.pb(ind);
      ind = p[len][ind];
      len--;
    }
    cout << sz(ans) << "\n";
    reverse(all(ans));
    for(int i = 0; i < sz(ans); i++){
      cout << ans[i] << " ";
    }
}

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