# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
57780 | 2018-07-16T05:48:20 Z | gnoor | Linear Garden (IOI08_linear_garden) | C++17 | 156 ms | 36340 KB |
#include <cstdio> #include <algorithm> using namespace std; int dp[1000100][3][3]; int main () { int n,m; scanf("%d%d",&n,&m); dp[0][0][0]=1; dp[0][1][1]=1; dp[0][2][2]=1; for (int i=1;i<n;i++) { for (int j=0;j<3;j++) { dp[i][j][0]=dp[i-1][j][1]; dp[i][j][1]=dp[i-1][j][0]+dp[i-1][j][2]; dp[i][j][1]%=m; dp[i][j][2]=dp[i-1][j][1]; } } for (int i=0;i<n;i++) { for (int j=0;j<3;j++) { dp[i][j][0]+=dp[i][j][1]+dp[i][j][2]; dp[i][j][0]%=m; } } char x; int mn=0; int mx=0; int cur=0; int ans=0; int nmx,nmn; for (int i=0;i<n;i++) { scanf(" %c",&x); if (x=='P') { cur++; nmx=max(mx,cur); nmn=min(mn,cur); if (nmx-nmn==1) { if (nmx==0) { ans+=dp[n-i-1][2+cur][0]+dp[n-i-1][1+cur][0]; } else { ans+=dp[n-i-1][1+cur][0]+dp[n-i-1][0+cur][0]; } ans--; } else if (nmx-nmn==2) { ans+=dp[n-i-1][cur-nmn][0]; } ans%=m; cur-=2; mx=max(mx,cur); mn=min(mn,cur); } else { cur++; mx=max(mx,cur); mn=min(mn,cur); } } ans++; ans%=m; printf("%d\n",(ans+m)%m); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 492 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 492 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 588 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 588 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 588 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 588 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 588 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 588 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 588 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 588 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 596 KB | Output is correct |
2 | Correct | 2 ms | 596 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 620 KB | Output is correct |
2 | Correct | 2 ms | 620 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 668 KB | Output is correct |
2 | Correct | 2 ms | 672 KB | Output is correct |
3 | Correct | 2 ms | 672 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 1312 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 1448 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 2892 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 3340 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 44 ms | 12116 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 57 ms | 15344 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 76 ms | 19056 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 91 ms | 23112 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 156 ms | 36336 KB | Output is correct |
2 | Correct | 147 ms | 36336 KB | Output is correct |
3 | Correct | 130 ms | 36340 KB | Output is correct |