Submission #440765

#TimeUsernameProblemLanguageResultExecution timeMemory
440765training4usacoLongest beautiful sequence (IZhO17_subsequence)C++11
40 / 100
6044 ms47024 KiB
#include <iostream> #include <vector> #include <algorithm> using namespace std; #define N 100000 int dp[N + 1]; int from[N + 1]; int a[N + 1]; int k[N + 1]; int store [1024][1024][11]; int main() { int n; cin >> n; // cout << n << endl; for(int i = 1; i <= n; ++i) { cin >> a[i]; } for(int i = 1; i <= n; ++i) { cin >> k[i]; } // best index if we have a mask for the first 10 bits and a mask for the second 10 bits and we need i setbits in the first 10 for(int i = 1; i <= n; ++i) { int lmask = a[i] >> 10; // top mask int rmask = a[i] & 1023; // bottom mask int best = 0; for(int m = 0; m < 1024; ++m) { int numset = __builtin_popcount(m & rmask); int need = k[i] - numset; if(need > 10 || need < 0) { continue; } if(dp[best] < dp[store[lmask][m][need]]) { best = store[lmask][m][need]; } } dp[i] = 1 + dp[best]; from[i] = best; for(int m = 0; m < 1024; ++m) { int numset =__builtin_popcount(m & lmask); if(dp[store[m][rmask][numset]] < dp[i]) { store[m][rmask][numset] = i; } } } int highest = 1; for(int i = 1; i <= n; ++i) { if(dp[highest] < dp[i]) { highest = i; } } vector<int> answer; while(highest) { answer.push_back(highest); highest = from[highest]; } sort(answer.begin(), answer.end()); cout << answer.size() << endl; for(int i = 0; i < (int)answer.size(); ++i) { cout << answer[i] << " "; } cout << endl; 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...