Submission #696243

#TimeUsernameProblemLanguageResultExecution timeMemory
696243nicolexxuuLongest beautiful sequence (IZhO17_subsequence)Java
0 / 100
1241 ms262144 KiB
import java.util.*; import java.io.*; public class subsequence { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int[] a = new int[n], k = new int[n]; int[] bc = new int[1<<10]; for(int i = 0; i < 1<<10; i++) bc[i] = Integer.bitCount(i); st = new StringTokenizer(br.readLine()); for(int i = 0; i < n; i++) a[i] = Integer.parseInt(st.nextToken()); st = new StringTokenizer(br.readLine()); for(int i = 0; i < n; i++) k[i] = Integer.parseInt(st.nextToken()); br.close(); int[][][][] dp = new int[1<<10][1<<10][11][2]; int[][] res = new int[n][2]; for(int i = 0; i < n; i++) { int par = -1, ans = 0; int l = a[i] >> 10; int r = a[i] - (l << 10); for(int j = 0; j < (1 << 10); j++) { // possible prev lefts int bLeft = k[i] - bc[l&j]; if(bLeft >= 0 && bLeft <= 10 ) { if(dp[l][r][bLeft][0] > ans) { ans = dp[l][r][bLeft][0]; par = dp[l][r][bLeft][1]; } } } res[i] = new int[] {ans+1, par}; for(int j = 0; j < (1 << 10); j++) { int b = bc[j&r]; if(ans+1 > dp[l][j][b][0]) { dp[l][j][b][0] = ans+1; dp[l][j][b][1] = i; } } } int idx = 0; for(int i = 0; i < n; i++) idx = (res[i][0] > res[idx][0]) ? i : idx; System.out.println(res[idx][0]); ArrayDeque<Integer> l = new ArrayDeque<>(); while(idx != -1) { l.add(idx); idx = res[idx][1]; } while(!l.isEmpty()) System.out.print(l.pollLast()+1 + " "); } } /* 4 1 2 3 4 10 0 1 0 5 5 3 5 3 5 10 1 20 1 20 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...