oj.uz

Submission #105227

# Submission time Handle Problem Language Result Execution time Memory
105227 2019-04-11T03:24:46 Z boatinw99 Linear Garden (IOI08_linear_garden) C++14
100 / 100
 356 ms 65144 KB 
#include<bits/stdc++.h>
using namespace std ;
const int N = 1e6+9 ;
int n,md,ans=0,bit=0,mid=2 ;
int dp[2][3][3][5];///flip bit, max , min , sum
char s[N];
void update()
{
    for(int i=1;i<3;i++)for(int j=0;j<3;j++)for(int k=0;k<5;k++)
        dp[bit^1][i][j][k]=0;
    for(int i=1;i<3;i++)
    {
        for(int j=0;j<3;j++)
        {
            for(int k=0;k<5;k++)
            {
                int x=i,y=-j,sum=k-mid,tmp=dp[bit][i][j][k];
                if(abs(sum-x+1)<=2&&abs(sum-y+1)<=2)
                    dp[bit^1][max(sum+1,x)][j][k+1]=
                    (dp[bit^1][max(sum+1,x)][j][k+1]+tmp)%md;
                if(abs(sum-x-1)<=2&&abs(sum-y-1)<=2)
                    dp[bit^1][i][-min(sum-1,y)][k-1]=
                    (dp[bit^1][i][-min(sum-1,y)][k-1]+tmp)%md;
            }
        }
    }
    bit^=1;
}
void qans(int x,int mx,int mn,int sum)
{
    if(x>n)return ;
    int tmp1=sum ;
    if(s[x]=='P')tmp1--;
    else tmp1++;
    qans(x+1,max(mx,tmp1),min(mn,tmp1),tmp1);
    if(s[x]=='P')
    for(int i=1;i<3;i++)for(int j=0;j<3;j++)for(int k=0;k<5;k++)
    {
        int dx=i+sum,dy=-j+sum,sum=k-mid,tmp=dp[bit][i][j][k];
        if(abs(dx-mx)<=2&&abs(dx-mn)<=2&&abs(dy-mx)<=2&&abs(dy-mn)<=2)
            ans=(ans+tmp)%md;
    }
    update();
}
main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    int i,j ;
    cin >> n >> md ;
    for(i=1;i<=n;i++)cin >> s[i] ;
    dp[0][1][0][mid+1]=1;
    qans(1,0,0,0);
    cout << (ans+1)%md ;
}

Compilation message

linear_garden.cpp: In function 'void qans(int, int, int, int)':
linear_garden.cpp:39:32: warning: unused variable 'sum' [-Wunused-variable]
         int dx=i+sum,dy=-j+sum,sum=k-mid,tmp=dp[bit][i][j][k];
                                ^~~
linear_garden.cpp: At global scope:
linear_garden.cpp:45:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
linear_garden.cpp: In function 'int main()':
linear_garden.cpp:48:11: warning: unused variable 'j' [-Wunused-variable]
     int i,j ;
           ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 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 428 KB Output is correct

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
4.0 / 4.0

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

Subtask #7
4.0 / 4.0

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

Subtask #8
4.0 / 4.0

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

Subtask #9
4.0 / 4.0

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

Subtask #10
4.0 / 4.0

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

Subtask #11
4.0 / 4.0

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

Subtask #12
5.0 / 5.0

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

Subtask #13
5.0 / 5.0

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

Subtask #14
5.0 / 5.0

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

Subtask #15
5.0 / 5.0

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

Subtask #16
5.0 / 5.0

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

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4356 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 5108 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 20452 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 26456 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 33464 KB Output is correct

Subtask #22
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 40760 KB Output is correct

Subtask #23
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 64888 KB Output is correct
2 Correct 319 ms 65144 KB Output is correct
3 Correct 356 ms 65116 KB Output is correct