# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
366515 | nicolaalexandra | Longest beautiful sequence (IZhO17_subsequence) | C++14 | 4 ms | 4716 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define DIMN 100010
#define DIM (1<<10) + 2
using namespace std;
int v[DIMN],w[DIMN],dp[DIMN],fth[DIMN];
int poz[DIM][DIM][11];
vector <int> sol;
int n,i;
int main (){
//ifstream cin ("date.in");
//ofstream cout ("date.out");
cin>>n;
for (i=1;i<=n;i++)
cin>>v[i];
for (i=1;i<=n;i++)
cin>>w[i];
/// dp[i] - lg maxima a unei secv terminate cu i
/// poz[mask_left][mask_right][nr] - poz secv max care are conf mask_left+mask_right si iau nr biti de 1 din prima jumatate
int m = 10;
for (i=1;i<=n;i++){
int mask_right = (v[i] & ((1<<m)-1));
int mask_left = (v[i]>>m);
int maxi = 0, sol_poz = 0;
for (int mask=0;mask<(1<<m);mask++){
int cnt = w[i] - __builtin_popcount(mask & mask_right); /// atatia biti imi trb in stanga
if (cnt < 0 || cnt > m)
continue;
int x = poz[mask_left][mask][cnt];
if (dp[x] + 1 > dp[i]){
dp[i] = dp[x] + 1;
fth[i] = x;
}
}
/// actualizez dinamica
for (int mask=0;mask<(1<<m);mask++){
int cnt = (mask & mask_left);
if (dp[i] > dp[poz[mask][mask_right][cnt]])
poz[mask][mask_right][cnt] = i;
}
}
int maxi = 0, x = 0;
for (int i=1;i<=n;i++)
if (dp[i] > maxi){
maxi = dp[i];
x = i;
}
cout<<maxi<<"\n";
while (x){
sol.push_back(x);
x = fth[x];
}
for (i=sol.size()-1;i>=0;i--)
cout<<sol[i]<<" ";
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |