oj.uz

Submission #71891

# Submission time Handle Problem Language Result Execution time Memory
71891 2018-08-25T19:06:02 Z :p(#2229, exqt) Cross on the Grid (FXCUP3_cross) C++17
0 / 100
 3 ms 480 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 3 ms 480 KB Output is correct
4 Incorrect 2 ms 480 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 3 ms 480 KB Output is correct
4 Incorrect 2 ms 480 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 3 ms 480 KB Output is correct
4 Incorrect 2 ms 480 KB Output isn't correct
5 Halted 0 ms 0 KB -