제출 #393547

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
393547		SirCovidThe19th	Longest beautiful sequence (IZhO17_subsequence)	C++14	0 / 100	20 ms	45388 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;

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

    int popCnt[1024];
    for (int i = 0; i < 1024; i++) popCnt[i] = __builtin_popcount(i);

    
    static int dp[1024][1024][11];
    memset(dp, 0, sizeof(dp));
    //at index i what is the longest chain you can form
    int best[n+1];
    fill(best, best+n+1, 0);
    //at index i what is the first element in the longest
    //chain you can form so far
    int store[n+1];
    
    for (int i = 1; i <= n; i++){
        int right = a[i]&1023;
        int left = a[i]>>10;
        int idx = 0;

        for (int mask = 0; mask < 1024; mask++){
            int b = k[i]-popCnt[(right&mask)];
            if (b >= 0 and b <= 10)
                if (best[dp[left][mask][b]] > best[idx])
                    idx = dp[left][mask][b];
        }

        best[i] = best[idx]+1;
        store[i] = idx;

        for (int mask = 0; mask < 1024; mask++){
            int b = max(k[i]-(popCnt[(left&mask)]-popCnt[right]), 0);
            if (best[i] > best[dp[mask][right][b]])
                dp[mask][right][b] = i;
        }
    }

    int pos = max_element(best, best+n+1)-best;
    vector<int> res;
    while (pos != 0){
        res.push_back(pos);
        pos = store[pos];
    }
    reverse(res.begin(), res.end());
    cout<<res.size()<<endl;
    for (int i = 0; i < res.size(); i++) cout<<res[i]<<" ";
} 

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

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

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