Submission #71891

#	Time	Username	Problem	Language	Result	Execution time	Memory
71891		:p (#119)	Cross on the Grid (FXCUP3_cross)	C++17	0 / 100	3 ms	480 KiB

cross

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int MOD = 1e9+7;

int main()
{
  int n; cin >> n;
  vector<array<ll, 4>> dp(n+1);

  dp[1] = {1, 0, 0, 0};
  dp[2] = {1, 0, 0, 0};

  for(int i=3; i<=n; i++)
  {
    dp[i][0] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2] + dp[i-1][3]) % MOD;
    dp[i][1] = (dp[i-1][0] + dp[i-1][3] - 2*dp[i-2][1] + 2*MOD) % MOD;
    dp[i][2] = (dp[i-1][0] - dp[i-2][2] + MOD) % MOD;
    dp[i][3] = (dp[i-1][0] + dp[i-1][1] - 2*dp[i-2][3] + 2*MOD) % MOD;

    // cout << dp[i][0] << ' ' << dp[i][1] << ' ' << dp[i][2] << ' ' << dp[i][3] << ' ' << endl;
  }

  cout << (dp[n][0] + dp[n][1] + dp[n][2] + dp[n][3])%MOD << endl;

  return 0;
}

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