CSES - HIIT Open 2019 - Results
Submission details
Task:Grid Paths
Sender:tykkipeli
Submission time:2019-05-25 12:04:37 +0300
Language:C++
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.04 sdetails

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll M = 1e9 + 7;

ll dp[101][101];
ll maara[101][101];

ll grid[101][101];

int main() {
   int n;
   cin >> n;
   for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> grid[i][j];
        }
   }
   dp[0][0] = grid[0][0];
   maara[0][0] = 1;
   for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == 0 && j == 0) continue;
            if (i > 0) {
                maara[i][j] += maara[i-1][j];
                maara[i][j] = maara[i][j]%M;
            }
            if (j > 0) {
                maara[i][j] += maara[i][j-1];
                maara[i][j] = maara[i][j]%M;
            }
            dp[i][j] = maara[i][j]*grid[i][j];
            dp[i][j] = dp[i][j] % M;
            if (i > 0) {
                dp[i][j] += dp[i-1][j];
                dp[i][j] = dp[i][j]%M;
            }
            if (j > 0) {
                dp[i][j] += dp[i][j-1];
                dp[i][j] = dp[i][j]%M;
            }
        }
   }
   cout << dp[n-1][n-1] << endl;
   
}

Test details

Test 1

Verdict: ACCEPTED

input
100
606755118 96655535 664126532 4...

correct output
530182530

user output
530182530