CSES - HIIT Open 2019 - Results
Submission details
Task:Grid Paths
Sender:.*
Submission time:2019-05-25 12:45:44
Language:C++
Status:READY
Result:
Test results
testverdicttime
#10.22 sdetails

Code

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define M 1000000007
#define N (1<<18)
#define P complex<long long>
#define X real()
#define Y imag()

using namespace std;

int n, rdk[101][101], rdk2[101][101], lah[111][111];
ll ans[101][101], tav[101][101], ans2;

void asd(int x, int y) {
	for(int i=0; i<=100; i++)
		for(int j=0; j<=100; j++)
			rdk2[i][j] = 0;
	rdk2[x][y-1] = 1;
	for(int i=x; i<=n; i++) {
		for(int j=y; j<=n; j++) {
			rdk2[i][j] = rdk2[i][j-1]+rdk2[i-1][j];
			rdk2[i][j] %= M;
		}
	}
	lah[x][y] = rdk2[n][n];
}

int main() {
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	cin >> n;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++)
			cin >> rdk[i][j];
	}
	tav[0][1] = 1;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			asd(i,j);
		}
	}
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			if(i == n && j == n) {
				tav[i][j] = tav[i][j-1]+tav[i-1][j];
				tav[i][j] %= M;
				ans[i][j] += rdk[i][j]*tav[i][j];
				ans[i][j] %= M;
				ans2 += ans[i][j];
				ans2 %= M;
				break;
			}
			tav[i][j] = tav[i][j-1]+tav[i-1][j];
			tav[i][j] %= M;
			ans[i][j] += rdk[i][j]*tav[i][j]*lah[i+1][j]+rdk[i][j]*tav[i][j]*lah[i][j+1];
			ans[i][j] %= M;
				ans2 += ans[i][j];
				ans2 %= M;
		}
	}
	cout << ans2;
}

Test details

Test 1

Verdict:

input
100
606755118 96655535 664126532 4...

correct output
530182530

user output
41756413