Submission #1152160

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152160		son2008	Linear Garden (IOI08_linear_garden)	C++20	100 / 100	284 ms	9188 KiB

linear_garden

#include<bits/stdc++.h>
using namespace std;
#define task "task"
#define ii pair<int,int>
#define fi first
#define se second
#define int long long
#define ll long long
#define ld double
#define mp make_pair
#define lg2 30
#define iii pair<int,ii>
#define iiii pair<ii,ii>
#define base 29
#define eps 1e-8
int dx[]= {0LL,0LL,1,-1,1,1,-1,-1};
int dy[]= {1,-1,0LL,0LL,1,-1,1,-1};
const int maxn=1e6+5;
const int mod=1e9+7;
int n,M,a[maxn];
void init()
{
    string s;
    cin>>n>>M>>s;
    for(int i=0;i<n;i++)
    {
        a[i+1]=s[i]=='P';
    }
}
//f[i][cnt][max][min][t]
void add(int &a,int b)
{
    a=(a+b)%M;
}
int f[2][5][5][5][2];
void process()
{
    f[0][2][2][2][0]=1;
    for(int i=0;i<n;i++)
    {
        for(int cnt=0;cnt<=4;cnt++)
        {
            for(int mx=2;mx<=4;mx++)
            {
                for(int mn=0;mn<=2;mn++)
                {
                    for(int t=0;t<=1;t++)
                    {
                        int cnt1=cnt-1,mx1=max(mx,cnt1),mn1=min(mn,cnt1);
                        if(mx1-mn1<=2)
                        {
                            add(f[(i+1)&1][cnt1][mx1][mn1][t||a[i+1]],f[i&1][cnt][mx][mn][t]);
                        }
                        cnt1=cnt+1,mx1=max(mx,cnt1),mn1=min(mn,cnt1);
                        if(mx1-mn1<=2&&(t||a[i+1]))
                        {
                            add(f[(i+1)&1][cnt1][mx1][mn1][t],f[i&1][cnt][mx][mn][t]);
                        }
                    }
                }
            }
        }
        memset(f[i&1],0,sizeof(f[i&1]));
    }
    int ans=0;
    for(int cnt=0;cnt<=4;cnt++)
    {
        for(int mx=2;mx<=4;mx++)
        {
            for(int mn=0;mn<=2;mn++)
            {
                for(int t=0;t<=1;t++)
                {
                    add(ans,f[n&1][cnt][mx][mn][t]);
                }
            }
        }
    }
    cout<<ans;
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if(fopen(task".inp","r"))
    {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    init();
    process();
    cerr <<endl<< "TIME : " << clock() * 0.001 << "s" << endl ;
}

Compilation message (stderr)

linear_garden.cpp: In function 'int main()':
linear_garden.cpp:88:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
linear_garden.cpp:89:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 2 / 2
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 4 / 4
• Subtask 7: 4 / 4
• Subtask 8: 4 / 4
• Subtask 9: 4 / 4
• Subtask 10: 4 / 4
• Subtask 11: 4 / 4
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5
• Subtask 20: 5 / 5
• Subtask 21: 5 / 5
• Subtask 22: 5 / 5
• Subtask 23: 5 / 5