TLAPM :The Last Problem | Please help getting wrong answer

help
1

I have gone through the editorial of this problem. I am still not able to find mistake in my code. can anyone please help what I am doing wrong.

problem statement:

code link :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int

int main() {
ll t;
cin>>t;

//precompute

ll arr[1001][1001];
ll val=1;
for(ll i=0;i<=1000;i++){
    ll row=0;
    for(ll j=i;j>=0;j--)
        arr[row++][j]=val++;    
}

while(t--)
{
     ll x1,y1,x2,y2;
     cin>>x1>>y1>>x2>>y2;
     ll sum1=0;
     
     x1--,x2--,y1--,y2--;
    for(ll i=x1;i<=x2;i++)
        sum1 += arr[i][y1];
    for(ll i=y1+1;i<=y2;i++)
        sum1 += arr[x2][i];
        
    cout<<sum1<<"\n";     
}
return 0;

}

2

Try the test case
1 1 1000 1000

The answer should be 1332833500.
But your is not matching

3

Your matrix formation is wrong.
Your matrix above non-principle diagonal or anti-diagonal or counter diagonal is okay.
But you haven’t written code for the values below that.
For instance arr[1000][1] you have not defined.

4

Thanks got it

5

Yeah a[1000][1000] won’t work because if you think logically like if you make the matrix of a[3][3]

Blockquote
1 2 4
3 5
6

indexing for them is like (1 - based )

Blockquote
11 12 13
21 22 23
31 32 33

if i ask you accordingly now what’s value a a[3][3] ? i.e. is nothing you can see in the first matrix
so for a[1000][1000] you have to make it a[2000][2000] cz then a[1000][1000] = 0

Hope you understand now!

6

I too facing issue with this problem
I don’t know why it is not working could you please help me
int a[][] = new int[1001][1001];
int i=1,j=1,k=1,l=1;
while(i<1001 && j<1001){
while(j>0){
a[i][j] = l;
l +=1;
i += 1;
j -= 1;
}

		i = 1;
		k +=1;
		j = k;
		
	}
	
	
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	int t = Integer.parseInt(br.readLine());
	int mod = 1000000007;
	while(t-->0){
		StringTokenizer st = new StringTokenizer(br.readLine());
		int x1 = Integer.parseInt(st.nextToken());
		int y1 = Integer.parseInt(st.nextToken());
		int x2 = Integer.parseInt(st.nextToken());
		int y2 = Integer.parseInt(st.nextToken());
		long dp[][] = new long[x2+1][y2+1];
		dp[x2][y2] = a[x2][y2];
		for(i=x2-1;i>=x1;i--)
			dp[i][x2]=((long)a[i][x2]%mod+dp[i+1][x2]%mod);
		for(i=y2-1;i>=y1;i--)
			dp[y2][i] = ((long)a[y2][i]%mod + dp[y2][i+1]%mod);
		for(i=x2-1;i>=x1;i--){
			for(j=y2-1;j>=y1;j--){
				dp[i][j] = ((long)a[i][j]%mod+Math.max(dp[i+1][j],dp[i][j+1])%mod)%mod;
			
			}
			
		}
		System.out.println(dp[x1][y1]);
		
	}
	}