1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
#include <iostream> using namespace std; int arr[105][105]; int s; int Matsum(int a,int b) { int p; int Line[105]; int max_end_here,max_so_far; for(int i=1;i<=s;i++) { p=0; for(int j=a;j<=b;j++) { p+=arr[j][i]; } Line[i]=p; } max_end_here=0; max_so_far=0; for(int i=1;i<=s;i++) { max_end_here+=Line[i]; if(max_end_here<0) max_end_here=0; if(max_end_here>max_so_far) max_so_far=max_end_here; } return max_so_far; } int main() { int t,mx,m; int b,r1,r2,c1,c2; cin>>t; while(t--) { cin>>s; cin>>b; mx =0; for(int i=0;i<=101;i++) for(int j=0;j<=101;j++) arr[i][j]=1; while(b--) { cin>>r1>>c1>>r2>>c2; for(int i=r1;i<=r2;i++) { for(int j=c1;j<=c2;j++) arr[i][j]=-10000000; } } for(int i=1;i<=s;i++) for(int j=1;j<=s;j++) { m = Matsum(i,j); if(mx<m) mx=m; } cout<<mx<<"\n"; } return 0; } |