fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <string>
  5. #include <cstdio>
  6. #include <cstring>
  7.  
  8. #define pb push_back
  9. using namespace std;
  10.  
  11. int main() {
  12.     ios_base::sync_with_stdio(0);
  13.     int T,r,c,k,x,y,i,j;
  14.     //freopen("inp.txt","r",stdin);
  15.     //freopen("out.txt","w",stdout);
  16.     cin>>T;
  17.     for(int t=1;t<=T;t++)
  18.     {
  19.         cin>>r>>c>>k;
  20.         int a[r][c];
  21.         int dp[r+1][c+1];
  22.         for(i=0;i<r;i++)
  23.         for(j=0;j<c;j++)
  24.         a[i][j]=0;
  25.  
  26.         for(i=0;i<=r;i++)
  27.         for(j=0;j<=c;j++) dp[i][j]=-1;
  28.  
  29.         for(i=0;i<k;i++)
  30.         {
  31.             cin>>x>>y;
  32.             a[x][y]=1;
  33.         }
  34.  
  35.         for(i=r-1;i>=0;i--)
  36.         for(j=c-1;j>=0;j--)
  37.         if(!a[i][j])  dp[i][j]=min(min(dp[i][j+1],dp[i+1][j]),dp[i+1][j+1])+1;
  38.  
  39.         long long sum=0;
  40.         for(i=0;i<r;i++)
  41.         for(j=0;j<c;j++)
  42.         if(!a[i][j]) sum+=dp[i][j]+1;
  43.  
  44.         cout<<"Case #"<<t<<": "<<sum<<"\n";
  45.     }
  46.     return 0;
  47. }
  48.  
Success #stdin #stdout 0s 16064KB
comments (?)
stdin
copy 
2
3 3 1
2 1
4 11 12
0 1
0 3
0 4
0 10
1 0
1 9
2 0
2 4
2 9
2 10
3 4
3 10
stdout
copy 
Case #1: 10
Case #2: 51
https://ideone.com/s5Nmw4
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!