Submission #71705

#	Time	Username	Problem	Language	Result	Execution time	Memory
71705		CODEFORCES_BLUE (#119)	Cross on the Grid (FXCUP3_cross)	C++98	57 / 100	1078 ms	828 KiB

cross

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
ll n, m, ans, dp[4][2]={1, 4, 1, 2, 1, 3, 1, 3}, temp[4];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int i, j, mod=1e9+7;
    cin>>n;
    for(i=2;i<n;i++)
    {
        temp[0]=(dp[0][1]+2*dp[1][1]%mod+dp[2][0])%mod;
        temp[1]=(dp[3][0]+dp[3][1])%mod;
        temp[2]=(dp[0][1]+2*dp[1][1]%mod)%mod;
        temp[3]=(dp[0][1]+dp[1][1]%mod+dp[2][0])%mod;
        for(j=0;j<4;j++)
        {
            dp[j][0]=dp[j][1];
            dp[j][1]=temp[j];
        }
    }
    cout<<dp[0][0];
}

• Subtask 1: 22 / 22
• Subtask 2: 35 / 35
• Subtask 3: 0 / 43