제출 #160859

#제출 시각아이디문제언어결과실행 시간메모리
160859MohamedAhmed0Longest beautiful sequence (IZhO17_subsequence)C++14
40 / 100
6077 ms182540 KiB
#include <bits/stdc++.h> using namespace std ; const int MAX = 1e5 + 10 ; const int Middle = 1 << 10 ; int arr[MAX] , arr2[MAX] , f[Middle][Middle][22] , idx[Middle][Middle][22] , prv[MAX] , ans[MAX] ; /*void print(int now) { if(now == -1) return ; print(prv[now]) ; cout<<now+1<<" " ; }*/ int main() { memset(f , -1 , sizeof(f)) ; ios_base::sync_with_stdio(0) ; cin.tie(0) ; int n ; cin>>n ; for(int i = 0 ; i < n ; ++i) cin>>arr[i] ; for(int i = 0 ; i < n ; ++i) cin>>arr2[i] ; int Max = 0 , en ; for(int i = 0 ; i < n ; ++i) { prv[i] = -1 ; ans[i] = 1 ; int valr = 0 , vall = 0 ; for(int j = 0 ; j <= 9 ; ++j) { if((arr[i] & (1 << j))) valr += (1 << j) ; if((arr[i] & (1 << (j+10)))) vall += (1 << j) ; } for(int j = 0 ; j < (1 << 10) ; ++j) { int x = __builtin_popcount((vall & j)) ; if(x > arr2[i]) continue ; if(f[j][valr][arr2[i] - x] + 1 > ans[i]) ans[i] = f[j][valr][arr2[i] - x] + 1 , prv[i] = idx[j][valr][arr2[i] - x] ; } for(int j = 0 ; j < (1 << 10) ; ++j) { int x = __builtin_popcount((valr & j)) ; if(ans[i] > f[vall][j][x]) f[vall][j][x] = ans[i] , idx[vall][j][x] = i ; } if(ans[i] > Max) Max = ans[i] , en = i ; } cout<<Max<<"\n" ; vector<int>v ; int cur = en ; while(1) { if(cur == -1) break ; v.push_back(cur) ; //debugging if(v.size() > n) assert(0) ; cur = prv[cur] ; } reverse(v.begin() , v.end()) ; for(auto &i : v) cout<<i+1<<" " ; return 0 ; }

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

subsequence.cpp: In function 'int main()':
subsequence.cpp:67:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(v.size() > n)
      ~~~~~~~~~^~~
subsequence.cpp:60:6: warning: 'en' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int cur = en ;
      ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...