— Dark mode

Datatähti 2025 alku

Niitty

  • Start: 2024-10-28 00:00:00
  • End: 2024-11-11 00:00:00
Submission details
Task:Niitty
Sender:maweiyin24562
Submission time:2024-10-31 12:18:06 +0200
Language:C++ (C++11)
Status:READY
Result:58
Feedback
groupverdictscore
#1ACCEPTED4
#2ACCEPTED6
#3ACCEPTED10
#4ACCEPTED13
#5ACCEPTED25
#60
Test results
testverdicttimegroup
#1ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#2ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#3ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#4ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#5ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#6ACCEPTED0.00 s2, 3, 4, 5, 6details
#7ACCEPTED0.00 s2, 3, 4, 5, 6details
#8ACCEPTED0.00 s2, 3, 4, 5, 6details
#9ACCEPTED0.00 s2, 3, 4, 5, 6details
#10ACCEPTED0.01 s3, 4, 5, 6details
#11ACCEPTED0.01 s3, 4, 5, 6details
#12ACCEPTED0.01 s3, 4, 5, 6details
#13ACCEPTED0.00 s3, 4, 5, 6details
#14ACCEPTED0.04 s4, 5, 6details
#15ACCEPTED0.07 s4, 5, 6details
#16ACCEPTED0.04 s4, 5, 6details
#17ACCEPTED0.01 s4, 5, 6details
#18ACCEPTED0.26 s5, 6details
#19ACCEPTED0.55 s5, 6details
#20ACCEPTED0.23 s5, 6details
#21ACCEPTED0.11 s5, 6details
#22--6details
#23--6details
#24--6details
#25--6details

Code

#include <bits/stdc++.h>

using namespace std;

#define IC(c) (int)(c-'A')

const int N=509;
const int F=26;
int n;

int pre[N][N][F];
int compact[N][F];
//pre[i][j][c] : prefix sum
//compact[j][c] for every array[top,btm]
//the compacted prefix sum
bool exi[F];
//do number c exists

int sum(int x1,int y1,int x2,int y2,int id){
	return pre[x2][y2][id]-pre[x1-1][y2][id]-pre[x2][y1-1][id]+pre[x1-1][y1-1][id];
}

bool check(int x1,int y1,int x2,int y2){
	if(exi[0]&&sum(x1,y1,x2,y2,0)==0)return 0;
	if(exi[1]&&sum(x1,y1,x2,y2,1)==0)return 0;
	if(exi[2]&&sum(x1,y1,x2,y2,2)==0)return 0;
	if(exi[3]&&sum(x1,y1,x2,y2,3)==0)return 0;
	if(exi[4]&&sum(x1,y1,x2,y2,4)==0)return 0;
	if(exi[5]&&sum(x1,y1,x2,y2,5)==0)return 0;
	if(exi[6]&&sum(x1,y1,x2,y2,6)==0)return 0;
	if(exi[7]&&sum(x1,y1,x2,y2,7)==0)return 0;
	if(exi[8]&&sum(x1,y1,x2,y2,8)==0)return 0;
	if(exi[9]&&sum(x1,y1,x2,y2,9)==0)return 0;
	if(exi[10]&&sum(x1,y1,x2,y2,10)==0)return 0;
	if(exi[11]&&sum(x1,y1,x2,y2,11)==0)return 0;
	if(exi[12]&&sum(x1,y1,x2,y2,12)==0)return 0;
	if(exi[13]&&sum(x1,y1,x2,y2,13)==0)return 0;
	if(exi[14]&&sum(x1,y1,x2,y2,14)==0)return 0;
	if(exi[15]&&sum(x1,y1,x2,y2,15)==0)return 0;
	if(exi[16]&&sum(x1,y1,x2,y2,16)==0)return 0;
	if(exi[17]&&sum(x1,y1,x2,y2,17)==0)return 0;
	if(exi[18]&&sum(x1,y1,x2,y2,18)==0)return 0;
	if(exi[19]&&sum(x1,y1,x2,y2,19)==0)return 0;
	if(exi[20]&&sum(x1,y1,x2,y2,20)==0)return 0;
	if(exi[21]&&sum(x1,y1,x2,y2,21)==0)return 0;
	if(exi[22]&&sum(x1,y1,x2,y2,22)==0)return 0;
	if(exi[23]&&sum(x1,y1,x2,y2,23)==0)return 0;
	if(exi[24]&&sum(x1,y1,x2,y2,24)==0)return 0;
	if(exi[25]&&sum(x1,y1,x2,y2,25)==0)return 0;
	return 1;
}

int cpc_sum(int l,int r,int id){
	return compact[r][id]-compact[l-1][id];
}

bool cpc_check(int l,int r){
	if(exi[0]&&cpc_sum(l,r,0)==0)return 0;
	if(exi[1]&&cpc_sum(l,r,1)==0)return 0;
	if(exi[2]&&cpc_sum(l,r,2)==0)return 0;
	if(exi[3]&&cpc_sum(l,r,3)==0)return 0;
	if(exi[4]&&cpc_sum(l,r,4)==0)return 0;
	if(exi[5]&&cpc_sum(l,r,5)==0)return 0;
	if(exi[6]&&cpc_sum(l,r,6)==0)return 0;
	if(exi[7]&&cpc_sum(l,r,7)==0)return 0;
	if(exi[8]&&cpc_sum(l,r,8)==0)return 0;
	if(exi[9]&&cpc_sum(l,r,9)==0)return 0;
	if(exi[10]&&cpc_sum(l,r,10)==0)return 0;
	if(exi[11]&&cpc_sum(l,r,11)==0)return 0;
	if(exi[12]&&cpc_sum(l,r,12)==0)return 0;
	if(exi[13]&&cpc_sum(l,r,13)==0)return 0;
	if(exi[14]&&cpc_sum(l,r,14)==0)return 0;
	if(exi[15]&&cpc_sum(l,r,15)==0)return 0;
	if(exi[16]&&cpc_sum(l,r,16)==0)return 0;
	if(exi[17]&&cpc_sum(l,r,17)==0)return 0;
	if(exi[18]&&cpc_sum(l,r,18)==0)return 0;
	if(exi[19]&&cpc_sum(l,r,19)==0)return 0;
	if(exi[20]&&cpc_sum(l,r,20)==0)return 0;
	if(exi[21]&&cpc_sum(l,r,21)==0)return 0;
	if(exi[22]&&cpc_sum(l,r,22)==0)return 0;
	if(exi[23]&&cpc_sum(l,r,23)==0)return 0;
	if(exi[24]&&cpc_sum(l,r,24)==0)return 0;
	if(exi[25]&&cpc_sum(l,r,25)==0)return 0;
	return true;
}

int ans;
//sum up answer
void Init(int i,int j,int id){
	pre[i][j][0]=pre[i-1][j][0]+pre[i][j-1][0]-pre[i-1][j-1][0];
   	pre[i][j][1]=pre[i-1][j][1]+pre[i][j-1][1]-pre[i-1][j-1][1];
	pre[i][j][2]=pre[i-1][j][2]+pre[i][j-1][2]-pre[i-1][j-1][2];
   	pre[i][j][3]=pre[i-1][j][3]+pre[i][j-1][3]-pre[i-1][j-1][3];
   	pre[i][j][4]=pre[i-1][j][4]+pre[i][j-1][4]-pre[i-1][j-1][4];
   	pre[i][j][5]=pre[i-1][j][5]+pre[i][j-1][5]-pre[i-1][j-1][5];
	pre[i][j][6]=pre[i-1][j][6]+pre[i][j-1][6]-pre[i-1][j-1][6];
   	pre[i][j][7]=pre[i-1][j][7]+pre[i][j-1][7]-pre[i-1][j-1][7];
   	pre[i][j][8]=pre[i-1][j][8]+pre[i][j-1][8]-pre[i-1][j-1][8];
   	pre[i][j][9]=pre[i-1][j][9]+pre[i][j-1][9]-pre[i-1][j-1][9];
   	pre[i][j][10]=pre[i-1][j][10]+pre[i][j-1][10]-pre[i-1][j-1][10];
   	pre[i][j][11]=pre[i-1][j][11]+pre[i][j-1][11]-pre[i-1][j-1][11];
	pre[i][j][12]=pre[i-1][j][12]+pre[i][j-1][12]-pre[i-1][j-1][12];
   	pre[i][j][13]=pre[i-1][j][13]+pre[i][j-1][13]-pre[i-1][j-1][13];
   	pre[i][j][14]=pre[i-1][j][14]+pre[i][j-1][14]-pre[i-1][j-1][14];
   	pre[i][j][15]=pre[i-1][j][15]+pre[i][j-1][15]-pre[i-1][j-1][15];
	pre[i][j][16]=pre[i-1][j][16]+pre[i][j-1][16]-pre[i-1][j-1][16];
   	pre[i][j][17]=pre[i-1][j][17]+pre[i][j-1][17]-pre[i-1][j-1][17];
   	pre[i][j][18]=pre[i-1][j][18]+pre[i][j-1][18]-pre[i-1][j-1][18];
   	pre[i][j][19]=pre[i-1][j][19]+pre[i][j-1][19]-pre[i-1][j-1][19];
   	pre[i][j][20]=pre[i-1][j][20]+pre[i][j-1][20]-pre[i-1][j-1][20];
   	pre[i][j][21]=pre[i-1][j][21]+pre[i][j-1][21]-pre[i-1][j-1][21];
	pre[i][j][22]=pre[i-1][j][22]+pre[i][j-1][22]-pre[i-1][j-1][22];
   	pre[i][j][23]=pre[i-1][j][23]+pre[i][j-1][23]-pre[i-1][j-1][23];
   	pre[i][j][24]=pre[i-1][j][24]+pre[i][j-1][24]-pre[i-1][j-1][24];
   	pre[i][j][25]=pre[i-1][j][25]+pre[i][j-1][25]-pre[i-1][j-1][25];
	pre[i][j][id]++;
}

int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			char c;
			cin>>c;
			int id=IC(c);
			exi[id]=true;
			Init(i,j,id);
		}
	//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))continue;
			int l=1,r=1;
			while(r<=n){
				compact[r][0]=sum(top,1,btm,r,0);
				compact[r][1]=sum(top,1,btm,r,1);
				compact[r][2]=sum(top,1,btm,r,2);
				compact[r][3]=sum(top,1,btm,r,3);
				compact[r][4]=sum(top,1,btm,r,4);
				compact[r][5]=sum(top,1,btm,r,5);
				compact[r][6]=sum(top,1,btm,r,6);
				compact[r][7]=sum(top,1,btm,r,7);
				compact[r][8]=sum(top,1,btm,r,8);
				compact[r][9]=sum(top,1,btm,r,9);
				compact[r][10]=sum(top,1,btm,r,10);
				compact[r][11]=sum(top,1,btm,r,11);
				compact[r][12]=sum(top,1,btm,r,12);
				compact[r][13]=sum(top,1,btm,r,13);
				compact[r][14]=sum(top,1,btm,r,14);
				compact[r][15]=sum(top,1,btm,r,15);
				compact[r][16]=sum(top,1,btm,r,16);
				compact[r][17]=sum(top,1,btm,r,17);
				compact[r][18]=sum(top,1,btm,r,18);
				compact[r][19]=sum(top,1,btm,r,19);
				compact[r][20]=sum(top,1,btm,r,20);
				compact[r][21]=sum(top,1,btm,r,21);
				compact[r][22]=sum(top,1,btm,r,22);
				compact[r][23]=sum(top,1,btm,r,23);
				compact[r][24]=sum(top,1,btm,r,24);
				compact[r][25]=sum(top,1,btm,r,25);
				while(cpc_check(l+1,r)&&l<r){
					l++;
				}
				if(cpc_check(l,r))ans+=l;
				r++;
			}
		}
	}

	cout<<ans<<endl;
	return 0;
}

Test details

Test 1

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

Verdict: ACCEPTED

input
10
TNCTNPNTPC
NPPNTNTPTP
NTNTTCNTCT
NPCPNPPNTT
...
view save

correct output
2035
view save

user output
2035
view save

Test 2

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

Verdict: ACCEPTED

input
10
NFWQLWNWYS
DZOQJVXFPJ
CNHXPXMCQD
QRTBVNLTQC
...
view save

correct output
9
view save

user output
9
view save

Test 3

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

Verdict: ACCEPTED

input
10
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
...
view save

correct output
3025
view save

user output
3025
view save

Test 4

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

Verdict: ACCEPTED

input
10
FFFFFFFFFF
FFFFFCFFFF
FFFFFFJFFF
FFFFFFFFFF
...
view save

correct output
12
view save

user output
12
view save

Test 5

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

Verdict: ACCEPTED

input
1
X
view save

correct output
1
view save

user output
1
view save

Test 6

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
20
BBCBUBOUOBBCUUBBCOUO
BOUCOOCUBCOOOCOBOCUO
UCCUUUOBCOCBCBUBUCOO
BUOBUCUCUOOBCOOUBUOO
...
view save

correct output
38724
view save

user output
38724
view save

Test 7

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
20
CBGLSHGZHYZDWBNDBJUG
SMUXOJQYPXZDTMJUIWOJ
XIDSTNBGHKRKOVUVMINB
MTQGCFRUHQKALXRNCQGS
...
view save

correct output
8334
view save

user output
8334
view save

Test 8

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
20
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
...
view save

correct output
44100
view save

user output
44100
view save

Test 9

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
20
AAAAAAAAXAAAAAAAAAAA
AAAWAAAAAAAAAAAAAOAA
AAAAAAAAAAAAAAAAAPAA
AAAAAAAAKAAAAAAAAAAZ
...
view save

correct output
18
view save

user output
18
view save

Test 10

Group: 3, 4, 5, 6

Verdict: ACCEPTED

input
50
GRGREEEGREGXRXXEGXXREXGRRRGRRR...
view save

correct output
1584665
view save

user output
1584665
view save

Test 11

Group: 3, 4, 5, 6

Verdict: ACCEPTED

input
50
AITIISJUHCCRZNKSDCNQKYSQRINFWJ...
view save

correct output
1077746
view save

user output
1077746
view save

Test 12

Group: 3, 4, 5, 6

Verdict: ACCEPTED

input
50
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...
view save

correct output
1625625
view save

user output
1625625
view save

Test 13

Group: 3, 4, 5, 6

Verdict: ACCEPTED

input
50
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFF...
view save

correct output
1680
view save

user output
1680
view save

Test 14

Group: 4, 5, 6

Verdict: ACCEPTED

input
100
NNCMDCDDCCNNNDNCMMNCDCDCCDCDNM...
view save

correct output
25325366
view save

user output
25325366
view save

Test 15

Group: 4, 5, 6

Verdict: ACCEPTED

input
100
LIMQQIHASECROEVILNVULGWZJPPKOG...
view save

correct output
22342463
view save

user output
22342463
view save

Test 16

Group: 4, 5, 6

Verdict: ACCEPTED

input
100
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTT...
view save

correct output
25502500
view save

user output
25502500
view save

Test 17

Group: 4, 5, 6

Verdict: ACCEPTED

input
100
QXQQQQQQQQQQQQQQQQQQQQQQQQQQQQ...
view save

correct output
25650
view save

user output
25650
view save

Test 18

Group: 5, 6

Verdict: ACCEPTED

input
200
NAANANMMKNKKAKMKMAKNKMNKMMNNAA...
view save

correct output
403292767
view save

user output
403292767
view save

Test 19

Group: 5, 6

Verdict: ACCEPTED

input
200
OMYWATTLURKQPTKEFMGGYAOONXWVSC...
view save

correct output
388111321
view save

user output
388111321
view save

Test 20

Group: 5, 6

Verdict: ACCEPTED

input
200
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCC...
view save

correct output
404010000
view save

user output
404010000
view save

Test 21

Group: 5, 6

Verdict: ACCEPTED

input
200
LLLLLLLLLLLLLLLLLHLLLLLLLLLLLL...
view save

correct output
14159445
view save

user output
14159445
view save

Test 22

Group: 6

Verdict:

input
500
VVHWVUHVHUWWWVUUUWVUUHUUWHWUVW...
view save

correct output
15683003812
view save

user output
(empty)

Test 23

Group: 6

Verdict:

input
500
OIMZGEQSBMBDSDXSWRFNKSGFEBBTJE...
view save

correct output
15575906951
view save

user output
(empty)

Test 24

Group: 6

Verdict:

input
500
IIIIIIIIIIIIIIIIIIIIIIIIIIIIII...
view save

correct output
15687562500
view save

user output
(empty)

Test 25

Group: 6

Verdict:

input
500
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWW...
view save

correct output
3058970930
view save

user output
(empty)

Tasks

A Pizzat-B Robotti-C Kortit I-D Kortit II-E Niitty-F Tikut-

Submissions (maweiyin24562)

2024-11-05 00:00:20 1002024-11-04 23:59:58 02024-11-04 23:41:46 582024-11-04 23:15:50 582024-11-04 23:15:22 02024-11-04 22:44:28 582024-11-04 22:43:26 02024-11-04 22:39:31 02024-11-04 19:51:41 582024-11-04 19:50:12 582024-11-04 19:49:57 02024-11-04 19:49:15 02024-11-04 19:49:00 02024-11-04 19:40:03 02024-11-04 19:39:46 02024-11-04 18:04:19 02024-11-04 16:44:28 582024-11-04 15:32:32 582024-11-04 15:32:19 02024-11-04 13:53:56 582024-11-04 13:53:32 02024-11-04 11:31:29 582024-11-04 11:31:03 582024-11-04 11:27:22 582024-11-04 11:27:05 02024-11-04 11:18:30 582024-11-04 11:16:30 582024-11-04 11:16:13 02024-11-04 11:15:56 582024-11-04 11:07:37 582024-11-04 09:41:52 02024-11-04 09:39:34 02024-11-03 22:10:50 582024-11-03 21:23:50 02024-11-03 17:55:49 582024-11-03 17:51:32 2024-11-03 17:23:58 582024-11-03 12:19:14 2024-11-03 12:13:27 582024-11-03 12:12:39 02024-11-02 23:40:02 582024-11-02 23:30:24 582024-11-02 23:23:46 582024-11-02 23:23:03 02024-11-02 23:22:31 02024-11-02 23:21:59 02024-11-02 23:15:10 582024-11-02 23:14:47 2024-11-02 23:10:17 582024-11-02 23:08:37 02024-11-02 23:08:21 02024-11-02 12:21:44 2024-11-02 12:20:46 2024-11-02 11:58:40 582024-10-31 13:37:56 2024-10-31 13:02:03 582024-10-31 12:50:43 582024-10-31 12:45:20 582024-10-31 12:44:15 582024-10-31 12:40:57 02024-10-31 12:39:43 02024-10-31 12:38:36 332024-10-31 12:37:18 42024-10-31 12:33:45 582024-10-31 12:30:20 42024-10-31 12:29:48 42024-10-31 12:18:06 582024-10-31 12:15:15 582024-10-31 12:13:44 582024-10-31 12:08:56 02024-10-31 11:57:15 2024-10-31 11:36:55 582024-10-30 15:19:48 582024-10-30 13:40:50 582024-10-30 13:24:32 582024-10-28 17:12:08 332024-10-28 09:50:11 332024-10-28 09:45:59 02024-10-28 09:42:22 02024-10-28 09:08:49 02024-10-28 03:44:15 02024-10-28 03:05:31 02024-10-28 02:49:52 02024-10-28 02:45:38 02024-10-28 02:40:41 0