Submission #927721

#	Time	Username	Problem	Language	Result	Execution time	Memory
927721		andrei_boaca	Misspelling (JOI22_misspelling)	C++17	28 / 100	4040 ms	156132 KiB

misspelling

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int mod=1e9+7;
int n,m;
int lastmare[500005],lastmic[500005];
int dp[3][27][500005]; /// 0 -> egal, 1 -> mai mic, 2 -> mai mare
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;
        if(a<b)
            lastmic[a]=max(lastmic[a],b);
        if(a>b)
            lastmare[b]=max(lastmare[b],a);
    }
    for(int i=1;i<=26;i++)
        dp[2][i][1]=1;
    for(int i=2;i<=n;i++)
    {
        int pmare=i,pmic=i;
        /// mai mare
        for(int j=i-1;j>=1;j--)
        {
            if(lastmic[j]>=i)
                break;
            pmare=j;
        }
        /// mai mic
        for(int j=i-1;j>=1;j--)
        {
            if(lastmare[j]>=i)
                break;
            pmic=j;
        }
        for(int c=1;c<=26;c++)
        {
            dp[0][c][i]=(1LL*dp[0][c][i-1]+1LL*dp[1][c][i-1]+1LL*dp[2][c][i-1])%mod;
            for(int j=i-1;j>=pmic;j--)
                for(int prv=1;prv<c;prv++)
                {
                    int val=(1LL*dp[1][prv][j]+1LL*dp[2][prv][j])%mod;
                    dp[1][c][i]=(dp[1][c][i]+val)%mod;
                }
            for(int j=i-1;j>=pmare;j--)
                for(int prv=c+1;prv<=26;prv++)
                {
                    int val=(1LL*dp[1][prv][j]+1LL*dp[2][prv][j])%mod;
                    dp[2][c][i]=(dp[2][c][i]+val)%mod;
                }
        }
    }
    int ans=0;
    for(int c=1;c<=26;c++)
    {
        ans=(ans+dp[0][c][n])%mod;
        ans=(ans+dp[1][c][n])%mod;
        ans=(ans+dp[2][c][n])%mod;
    }
    cout<<ans;
    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 20 / 20
• Subtask 3: 0 / 29
• Subtask 4: 0 / 32
• Subtask 5: 0 / 11