oj.uz

Submission #74729

# Submission time Handle Problem Language Result Execution time Memory
74729 2018-09-07T03:11:58 Z goodbaton Linear Garden (IOI08_linear_garden) C++14
100 / 100
 380 ms 6776 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>

using namespace std;
typedef long long ll;

#define SIZE 1000010

int main(){
  int dp[2][5][5][5][2] = {};
  int n,m;
  char s[SIZE];
  
  scanf("%d%d%s",&n,&m,s);

  dp[0][2][2][2][0] = 1;
  
  for(int i=0;i<n;i++){

    for(int j=2;j<=4;j++){
      for(int k=j-2;k<=3;k++){
	for(int l=k;l<=j;l++){
	  dp[1-i%2][j][k][l][0] = 0;
	  dp[1-i%2][j][k][l][1] = 0;
	}
      }
    }

    for(int j=2;j<=4;j++){
      for(int k=j-2;k<=3;k++){
	for(int l=k;l<=j;l++){
	  int now_dp0 = dp[i%2][j][k][l][0]%m;
	  int now_dp1 = dp[i%2][j][k][l][1]%m;
	  
	  if(s[i]=='L'){
	    if(l>0 && j-(l-1) <= 2)
	      dp[1-i%2][j][min(k,l-1)][l-1][0] += now_dp0;
	  }else{
	    if(l>0 && j-(l-1) <= 2)
	      dp[1-i%2][j][min(k,l-1)][l-1][1] += now_dp0;
	    
	    if(l<4 && l+1-k <= 2)
	      dp[1-i%2][max(j,l+1)][k][l+1][0] += now_dp0;
	  }
	  
	  if(l>0 && j-(l-1) <= 2)
	    dp[1-i%2][j][min(k,l-1)][l-1][1] += now_dp1;
	    
	  if(l<4 && l+1-k <= 2)
	    dp[1-i%2][max(j,l+1)][k][l+1][1] += now_dp1;
	}
      }
    }
  }

  int ans = 0;
  
  for(int j=2;j<=4;j++){
    for(int k=j-2;k<=3;k++){
      for(int l=k;l<=j;l++){
	ans += dp[n%2][j][k][l][0];
	ans += dp[n%2][j][k][l][1];
      }
    }
  }
  
  
  printf("%d\n",ans%m);
}

Compilation message

linear_garden.cpp: In function 'int main()':
linear_garden.cpp:16:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%s",&n,&m,s);
   ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 448 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 624 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 624 KB Output is correct

Subtask #6
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 624 KB Output is correct

Subtask #7
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 624 KB Output is correct

Subtask #8
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 624 KB Output is correct

Subtask #9
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 624 KB Output is correct

Subtask #10
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 624 KB Output is correct

Subtask #11
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 624 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 664 KB Output is correct
2 Correct 2 ms 668 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 672 KB Output is correct
2 Correct 2 ms 804 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 804 KB Output is correct
2 Correct 3 ms 804 KB Output is correct
3 Correct 3 ms 804 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 804 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 804 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 804 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1008 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 1580 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 2044 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 2676 KB Output is correct

Subtask #22
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 3364 KB Output is correct

Subtask #23
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 4816 KB Output is correct
2 Correct 338 ms 5796 KB Output is correct
3 Correct 380 ms 6776 KB Output is correct