제출 #1007334

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1007334		vqpahmad	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	3828 ms	175320 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[1025][1025][21];
    int main() {
        ios_base::sync_with_stdio(0);cin.tie(0);
	  memset(dp, 0, sizeof(dp));
     
     
        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 << ' ';
        }
    }

컴파일 시 표준 에러 (stderr) 메시지

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

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