CSES - Datatähti 2025 alku - Results
Submission details
Task:Niitty
Sender:maweiyin24562
Submission time:2024-11-02 23:40:02 +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.01 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.01 s4, 5, 6details
#15ACCEPTED0.03 s4, 5, 6details
#16ACCEPTED0.01 s4, 5, 6details
#17ACCEPTED0.01 s4, 5, 6details
#18ACCEPTED0.08 s5, 6details
#19ACCEPTED0.23 s5, 6details
#20ACCEPTED0.06 s5, 6details
#21ACCEPTED0.05 s5, 6details
#22--6details
#23--6details
#240.94 s6details
#25--6details

Code

#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 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)
				while(check(top,l+1,btm,r)&&l<r){
					l++;
				}
				if(tag)ans+=l;
				else if(check(top,l,btm,r)){tag=true,ans+=l;}
				r++;
			}
		}
	}

 printf("%d\n",ans);
	return 0;
}

Test details

Test 1

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

Verdict: ACCEPTED

input
10
TNCTNPNTPC
NPPNTNTPTP
NTNTTCNTCT
NPCPNPPNTT
...

correct output
2035

user output
2035

Test 2

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

Verdict: ACCEPTED

input
10
NFWQLWNWYS
DZOQJVXFPJ
CNHXPXMCQD
QRTBVNLTQC
...

correct output
9

user output
9

Test 3

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

Verdict: ACCEPTED

input
10
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
...

correct output
3025

user output
3025

Test 4

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

Verdict: ACCEPTED

input
10
FFFFFFFFFF
FFFFFCFFFF
FFFFFFJFFF
FFFFFFFFFF
...

correct output
12

user output
12

Test 5

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

Verdict: ACCEPTED

input
1
X

correct output
1

user output
1

Test 6

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
20
BBCBUBOUOBBCUUBBCOUO
BOUCOOCUBCOOOCOBOCUO
UCCUUUOBCOCBCBUBUCOO
BUOBUCUCUOOBCOOUBUOO
...

correct output
38724

user output
38724

Test 7

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
20
CBGLSHGZHYZDWBNDBJUG
SMUXOJQYPXZDTMJUIWOJ
XIDSTNBGHKRKOVUVMINB
MTQGCFRUHQKALXRNCQGS
...

correct output
8334

user output
8334

Test 8

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
20
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
...

correct output
44100

user output
44100

Test 9

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
20
AAAAAAAAXAAAAAAAAAAA
AAAWAAAAAAAAAAAAAOAA
AAAAAAAAAAAAAAAAAPAA
AAAAAAAAKAAAAAAAAAAZ
...

correct output
18

user output
18

Test 10

Group: 3, 4, 5, 6

Verdict: ACCEPTED

input
50
GRGREEEGREGXRXXEGXXREXGRRRGRRR...

correct output
1584665

user output
1584665

Test 11

Group: 3, 4, 5, 6

Verdict: ACCEPTED

input
50
AITIISJUHCCRZNKSDCNQKYSQRINFWJ...

correct output
1077746

user output
1077746

Test 12

Group: 3, 4, 5, 6

Verdict: ACCEPTED

input
50
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

correct output
1625625

user output
1625625

Test 13

Group: 3, 4, 5, 6

Verdict: ACCEPTED

input
50
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFF...

correct output
1680

user output
1680

Test 14

Group: 4, 5, 6

Verdict: ACCEPTED

input
100
NNCMDCDDCCNNNDNCMMNCDCDCCDCDNM...

correct output
25325366

user output
25325366

Test 15

Group: 4, 5, 6

Verdict: ACCEPTED

input
100
LIMQQIHASECROEVILNVULGWZJPPKOG...

correct output
22342463

user output
22342463

Test 16

Group: 4, 5, 6

Verdict: ACCEPTED

input
100
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTT...

correct output
25502500

user output
25502500

Test 17

Group: 4, 5, 6

Verdict: ACCEPTED

input
100
QXQQQQQQQQQQQQQQQQQQQQQQQQQQQQ...

correct output
25650

user output
25650

Test 18

Group: 5, 6

Verdict: ACCEPTED

input
200
NAANANMMKNKKAKMKMAKNKMNKMMNNAA...

correct output
403292767

user output
403292767

Test 19

Group: 5, 6

Verdict: ACCEPTED

input
200
OMYWATTLURKQPTKEFMGGYAOONXWVSC...

correct output
388111321

user output
388111321

Test 20

Group: 5, 6

Verdict: ACCEPTED

input
200
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCC...

correct output
404010000

user output
404010000

Test 21

Group: 5, 6

Verdict: ACCEPTED

input
200
LLLLLLLLLLLLLLLLLHLLLLLLLLLLLL...

correct output
14159445

user output
14159445

Test 22

Group: 6

Verdict:

input
500
VVHWVUHVHUWWWVUUUWVUUHUUWHWUVW...

correct output
15683003812

user output
(empty)

Test 23

Group: 6

Verdict:

input
500
OIMZGEQSBMBDSDXSWRFNKSGFEBBTJE...

correct output
15575906951

user output
(empty)

Test 24

Group: 6

Verdict:

input
500
IIIIIIIIIIIIIIIIIIIIIIIIIIIIII...

correct output
15687562500

user output
-1492306684

Test 25

Group: 6

Verdict:

input
500
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWW...

correct output
3058970930

user output
(empty)