제출 #679067

#제출 시각아이디문제언어결과실행 시간메모리
679067grandmast3rLongest beautiful sequence (IZhO17_subsequence)C++17
40 / 100
6097 ms126192 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define vi vector<int> #define pii pair<int, int> #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #ifdef ON_PC freopen("input.txt", "r", stdin); #endif // freopen("output.txt", "w", stdout); int T = 1; // cin >> T; while (T--){ int n; cin >> n; vector<int> a(n + 1); for (int i = 1; i <= n; i++){ cin >> a[i]; } vector<int> k(n + 1); for (int i = 1; i <= n; i++){ cin >> k[i]; } vector<int> dp(n + 1, 1); vector<int> p(n + 1); vector<vector<vector<pair<int, int>>>> mx((1 << 10), vector<vector<pair<int, int>>>((1 << 10), vector<pair<int, int>>(11, {-1, -1}))); for (int i = 1; i <= n; i++){ for (int x = 0; x < (1 << 10); x++){ int cur = __builtin_popcount((x << 10) & a[i]); if (k[i] - cur >= 0 && k[i] - cur <= 10){ pair<int, int> q = mx[x][a[i] & ((1 << 10) - 1)][k[i] - cur]; if (q.second != -1 && q.first + 1 > dp[i]){ dp[i] = q.first + 1; p[i] = q.second; } } } for (int y = 0; y < (1 << 10); y++){ int cnt = __builtin_popcount((a[i] & ((1 << 10) - 1)) & y); mx[(a[i] >> 10)][y][cnt] = max(mx[(a[i] >> 10)][y][cnt], {dp[i], i}); } } int v = 1; for (int i = 1; i <= n; i++){ if (dp[i] > dp[v]){ v = i; } } vector<int> res; while (v){ res.push_back(v); v = p[v]; } reverse(all(res)); cout << res.size() << "\n"; for (int i = 0; i < res.size(); i++){ cout << res[i] << " "; } cout << "\n"; } return 0; }

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

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