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