Submission #1007329

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007329		vqpahmad	Longest beautiful sequence (IZhO17_subsequence)	C++17	7 / 100	226 ms	163536 KiB

subsequence

    #include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    #define endl '\n'
    #define FF first
    #define SS second
    #define all(a) a.begin(), a.end()
    #define mdo (ll)(1000000007)
     
  //vector<vector<vector<array<int, 2>>>> dp(1024, vector<vector<array<int, 2>>>(1024, vector<array<int, 2>>(20)));
  array<int, 2> dp[1024][1024][20];
    int main() {
        ios_base::sync_with_stdio(0);cin.tie(0);
     
     
        int n;
        cin >> n;
     
        vector<int> A(n), K(n);
        for (int i = 0; i < n; i++) {
            cin >> A[i];
        }
        for (int i = 0; i < n; i++) {
            cin >> K[i];
        }
     
        int ans = 0, ind = 0;
        vector<int> Prv(n, -1);
        for (int i = 0; i < n; i++) {
            int low = 0, up = 0;
            for (int j = 0; j < 10; j++) {
                low += ((1 << j) & A[i]);
            }
            for (int j = 10; j < 20; j++) {
                if ((1 << j) & A[i]) {
                    up += (1 << (j - 10));
                }
            }
     
            int res = 1;
            for (int x = 0; x < (1 << 10); x++) {
                if (K[i] - __builtin_popcount(x & low) < 0) {
                    continue;
                }
                if (dp[x][up][K[i] - __builtin_popcount(x & low)][0] + 1 > res) {
                    res = dp[x][up][K[i] - __builtin_popcount(x & low)][0] + 1;
                    Prv[i] = dp[x][up][K[i] - __builtin_popcount(x & low)][1];
                }
            }
     
            if (res > ans) {
                ind = i, ans = res;
            }
            for (int x = 0; x < (1 << 10); x++) {
                if (res > dp[low][x][__builtin_popcount(x & up)][0]) {
                    dp[low][x][__builtin_popcount(x & up)][0] = res;
                    dp[low][x][__builtin_popcount(x & up)][1] = i;
                }
            }
     
        }
     
     
        vector<int> Ans;
        Ans.push_back(ind);
        while (Prv[ind] != -1) {
            ind = Prv[ind];
            Ans.push_back(ind);
        }
     
        cout << Ans.size() << endl;
        reverse(all(Ans));
        for (int i = 0; i < Ans.size(); i++) {
            cout << Ans[i] + 1 << ' ';
        }
    }

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:73:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for (int i = 0; i < Ans.size(); i++) {
      |                         ~~^~~~~~~~~~~~

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