Niitty

input/code.cpp: In function 'int main()':
input/code.cpp:61:30: warning: unused variable 'tag' [-Wunused-variable]
   61 |                         bool tag=false;
      |                              ^~~

#include <bits/stdc++.h>
 
using namespace std;
 
#define IC(c) (int)(c-'A')
 
#define sum(x1,y1,x2,y2,id) pre[x2][y2][id]-pre[x1-1][y2][id]-pre[x2][y1-1][id]+pre[x1-1][y1-1][id]
const int N=509;
const int F=26;
int n,C;
 
int pre[N][N][F+1];
//pre[i][j][c] : prefix sum
//compact[j][c] for every array[top,btm]
//the compacted prefix sum
int idx[F+1];//char-int list
bool vst[N][N];
//record if (x,y) (righttop) is visited
 
bool check(int x1,int y1,int x2,int y2){
	for(int i=1;i<=C;i++)
		if(sum(x1,y1,x2,y2,i)==0)
			return false;
	return true;
}
int ans;
//sum up answer
 
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			char c;
			cin>>c;
			int id=IC(c);
			if(!idx[id]){
				C++;
				idx[id]=C;
			}
			for(int k=1;k<=C;k++){
				if(k==idx[id])
					pre[i][j][k]=pre[i-1][j][k]+pre[i][j-1][k]-pre[i-1][j-1][k]+1;
				else
					pre[i][j][k]=pre[i-1][j][k]+pre[i][j-1][k]-pre[i-1][j-1][k];
			}
		}
	//input ends here
	//for every [top,btm] in [1,n]
	for(int top=1;top<=n;top++){
		for(int btm=top;btm<=n;btm++){//O(n^2)
			if(!check(top,1,btm,n)){
				if(btm==n){
					cout<<ans<<endl;
					return 0;
				}
				else continue;
			}
			int l=1,r=1;
			//scan the array
			bool tag=false;
			while(r<=n){//O(n)
				if(vst[top][r]&&btm==n){r++;continue;}
				while(check(top,l+1,btm,r)&&l<r)l++;
				if(check(top,l,btm,r)){
					ans+=l*(n-btm+1);//
					vst[top][r]=true;
				}
				r++;
			}
		}
	}
 
 printf("%d\n",ans);
	return 0;
}

Test 1

Group: 1, 2, 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 2

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 4

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

Test 6

Group: 2, 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 7

Group: 2, 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 8

Group: 2, 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 9

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

Test 10

Group: 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 11

Group: 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 12

Group: 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 13

Group: 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 14

Group: 4, 5, 6

Verdict: WRONG ANSWER

Test 15

Group: 4, 5, 6

Verdict: WRONG ANSWER

Test 16

Group: 4, 5, 6

Verdict: WRONG ANSWER

Test 17

Group: 4, 5, 6

Verdict: WRONG ANSWER

Test 18

Group: 5, 6

Verdict: WRONG ANSWER

Test 19

Group: 5, 6

Verdict: WRONG ANSWER

Test 20

Group: 5, 6

Verdict: WRONG ANSWER

Test 21

Group: 5, 6

Verdict: WRONG ANSWER

Test 22

Group: 6

Verdict: TIME LIMIT EXCEEDED

Test 23

Group: 6

Verdict: TIME LIMIT EXCEEDED

Test 24

Group: 6

Verdict: TIME LIMIT EXCEEDED

Test 25

Group: 6

Verdict: TIME LIMIT EXCEEDED