Here’s my code for the problem timber auction from the IARCS Problem Archive, it gets wrong answer on surprisingly ALL the test cases. It seems to work correctly for all the test cases I’ve tried. I’m using DP and inclusion-exclusion in order to compute sum…
#include <iostream>
#include <cstdio>
using namespace std;
int main(void)
{
int n, m, x1, y1, x2, y2, tmp;
scanf("%d%d", &n, &m);
int sum[n][m];
for(int i = 0;i < n;i++)
{
for(int j = 0;j < m;j++)
{
scanf("%d", &tmp);
if(i == 0 && j == 0)
{
sum[i][j] = tmp;
}
else if(i == 0)
{
sum[i][j] = tmp + sum[i][j-1];
}
else if(j == 0)
{
sum[i][j] = tmp + sum[i-1][j];
}
else
sum[i][j] = tmp + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
}
}
for(int i = 0;i < n;i++)
{
for(int j = 0;j < m;j++)
{
printf("%d ", sum[i][j]);
}
printf("\n");
}
int c;
scanf("%d", &c);
while(c--)
{
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
int i = x1-1, j =y1-1, k=x2-1, l = y2-1;
int ans = sum[k][l];
if(i > 0)
ans -= sum[i-1][l];
if(j > 0)
ans -= sum[k][j-1];
if(i > 0 && j > 0)
ans += sum[i-1][j-1];
printf("%d\n", ans);
}
}