제출 #343367

#제출 시각아이디문제언어결과실행 시간메모리
343367ivan_tudorLongest beautiful sequence (IZhO17_subsequence)C++14
0 / 100
2 ms492 KiB
#include<bits/stdc++.h> using namespace std; int dp[1030][15][1030]; const int N = 1e5 + 5; int v[N]; int k[N]; int rsp[N], lst[N]; void print(int nod){ if(nod == 0) return; print(lst[nod]); cout<<nod<<" "; } int main() { //freopen(".in","r",stdin); ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); int n; cin>>n; for(int i = 1; i<=n;i++){ cin>>v[i]; } for(int i=1;i<=n;i++){ cin>>k[i]; } int pans = 0; for(int i =1; i<=n;i++){ int mr = v[i] & ((1<<10) - 1); int ml = v[i]>>10; for(int mask = 0; mask < (1<<10);mask ++){ int rms = k[i] - __builtin_popcount(mask & ml); if(rsp[i] < rsp[ dp[mask][rms][mr] ]){ rsp[i] = rsp[ dp[mask][rms][mr]]; lst[i] = dp[mask][rms][mr]; } } rsp[i] ++; for(int mask =0 ; mask < (1<<10); mask++){ int nr = __builtin_popcount(mask & mr); int &cur = dp[ml][nr][mask]; if(rsp[cur] < rsp[i]) cur = i; } if(rsp[i] > rsp[pans]) pans = i; } cout<<rsp[pans]<<"\n"; print(pans); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...