fork(5) download 
  1. #include <stdio.h>
  2.  
  3. int A[1005], B[1005];
  4. int dp[2][1005][55][55];
  5.  
  6. int max(int a, int b){ return a > b ? a : b; }
  7.  
  8. int main(){
  9.     int n, p, k;
  10.     scanf("%d%d%d", &n, &p, &k);
  11.     if(k == 0){ printf("0"); return 0; }
  12.     if(p > 2*((n+k-1)/k)) p = 2*((n+k-1)/k);
  13.     int r;
  14.     scanf("%d", &r);
  15.     for(int i=0; i<r; i++){
  16.         int x;
  17.         scanf("%d", &x);
  18.         A[x] = 1;
  19.     }
  20.     int s;
  21.     scanf("%d", &s);
  22.     for(int i=0; i<s; i++){
  23.         int x;
  24.         scanf("%d", &x);
  25.         B[x] = 1;
  26.     }
  27.     for(int i=0; i<2; i++) for(int j=0; j<1005; j++) for(int k=0; k<55; k++) for(int p=0; p<55; p++) dp[i][j][k][p] = -1e9;
  28.     dp[0][0][0][0] = 0;
  29.     for(int i=1; i<=n; i++){
  30.         int cur = i&1, prev = !cur;
  31.         // A only
  32.         // - From nothing
  33.         for(int j=1; j<=p; j++) dp[cur][j][k-1][0] = max(dp[cur][j][k-1][0], dp[prev][j-1][0][0] + A[i]);
  34.         // - From something
  35.         for(int j=1; j<=p; j++) for(int a=0; a<k-1; a++) dp[cur][j][a][0] = max(dp[cur][j][a][0], dp[prev][j][a+1][0] + A[i]);
  36.  
  37.         // B only
  38.         // - From nothing
  39.         for(int j=1; j<=p; j++) dp[cur][j][0][k-1] = max(dp[cur][j][0][k-1], dp[prev][j-1][0][0] + B[i]);
  40.         // - From something
  41.         for(int j=1; j<=p; j++) for(int b=0; b<k-1; b++) dp[cur][j][0][b] = max(dp[cur][j][0][b], dp[prev][j][0][b+1] + B[i]);
  42.  
  43.         // A and B
  44.         // - From some A
  45.         for(int j=1; j<=p; j++) for(int a=0; a<k-1; a++) dp[cur][j][a][k-1] = max(dp[cur][j][a][k-1], dp[prev][j-1][a+1][0] + (A[i]|B[i]));
  46.         // - From some B
  47.         for(int j=1; j<=p; j++) for(int b=0; b<k-1; b++) dp[cur][j][k-1][b] = max(dp[cur][j][k-1][b], dp[prev][j-1][0][b+1] + (A[i]|B[i]));
  48.         // - From some A and B
  49.         for(int j=2; j<=p; j++) for(int a=0; a<k-1; a++) for(int b=0; b<k-1; b++) dp[cur][j][a][b] = max(dp[cur][j][a][b], dp[prev][j][a+1][b+1] + (A[i]|B[i]));
  50.  
  51.         // None
  52.         for(int j=0; j<=p; j++) dp[cur][j][0][0] = max(dp[cur][j][0][0], dp[prev][j][0][0]);
  53.  
  54.         for(int j=0; j<=p; j++) for(int a=0; a<k; a++) for(int b=0; b<k; b++) dp[prev][j][a][b] = -1e9;
  55.     }
  56.     int res = -1e9;
  57.     for(int i=0; i<=p; i++) for(int j=0; j<k; j++) for(int a=0; a<k; a++) res = max(res, dp[n&1][i][j][a]);
  58.     printf("%d", res);
  59.     return 0;
  60. }
Runtime error #stdin #stdout 0s 39824KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/cwP55b
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!