CSES - Datatähti 2025 alku - Results
Submission details
Task:Niitty
Sender:PMak
Submission time:2024-11-01 18:41:16 +0200
Language:C++ (C++17)
Status:READY
Result:33
Feedback
groupverdictscore
#1ACCEPTED4
#2ACCEPTED6
#3ACCEPTED10
#4ACCEPTED13
#50
#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.01 s2, 3, 4, 5, 6details
#10ACCEPTED0.01 s3, 4, 5, 6details
#11ACCEPTED0.03 s3, 4, 5, 6details
#12ACCEPTED0.00 s3, 4, 5, 6details
#13ACCEPTED0.05 s3, 4, 5, 6details
#14ACCEPTED0.01 s4, 5, 6details
#15ACCEPTED0.15 s4, 5, 6details
#16ACCEPTED0.01 s4, 5, 6details
#17ACCEPTED0.91 s4, 5, 6details
#18ACCEPTED0.04 s5, 6details
#19ACCEPTED0.78 s5, 6details
#20ACCEPTED0.02 s5, 6details
#21--5, 6details
#22ACCEPTED0.30 s6details
#23--6details
#24ACCEPTED0.22 s6details
#25--6details

Compiler report

input/code.cpp:22:19: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
   22 | void print(vector<auto> v) {
      |                   ^~~~

Code

#include <bits/stdc++.h>
#define F0R(i, n) for (i=0; i<n; i++)
#define FOR(i, from, to) for (i = from; i < to; i++)
#define R0F(n) for (int i = n; i>=0; --i)
#define ROF(from, to) for (int i = from; i >= to; --i)
#define ll long long
#define mod (int) (1e9 + 7)
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define pii pair<int, int>
#define pci pair<char, int>
#define pll pair<ll, ll>
#define YES cout << "YES\n";
#define NO cout << "NO\n";
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
using namespace std;
void print(vector<auto> v) {
for (auto it = v.begin(); it != v.end(); ++it)
cout << *it << " ";
cout << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, i, j, k, a, b;
ll ans = 0ll;
char t;
cin >> n;
vector<vi> grid(n, vi(n, 0));
set<int> chars;
map<char, int> mp;
int alphabets = 0;
F0R(i, n) {
F0R (j, n) {
cin >> t;
if (mp.find(t) != mp.end())
grid[i][j] = mp[t];
else {
mp[t] = alphabets;
grid[i][j] = alphabets++;
chars.insert(alphabets);
}
}
}
// for (auto v : grid)
// print(v);
vector<vector<vi>> dp(n, vector<vi>(n, vi(alphabets, 0)));
F0R (i, n) {
F0R (j, n) {
F0R (k, alphabets) {
if (i == 0 && j == 0)
dp[i][j][k] = (grid[i][j] == k);
else if (i == 0)
dp[i][j][k] = dp[i][j-1][k] + (grid[i][j] == k);
else if (j == 0)
dp[i][j][k] = dp[i-1][j][k] + (grid[i][j] == k);
else
dp[i][j][k] = dp[i-1][j][k] + dp[i][j-1][k] - dp[i-1][j-1][k] + (grid[i][j] == k);
}
// printf("(%d, %d), A=%d, K=%d, B=%d\n", i, j, dp[i][j][0], dp[i][j][1], dp[i][j][2]);
}
}
bool all = false; int max_b = n;
vi c(alphabets, 0);
F0R (i, n) {
F0R (j, n) {
max_b = n;
FOR (a, i, n) {
FOR (b, j, max_b) {
fill(c.begin(), c.end(), 0);
all = true;
if (i == 0 && j == 0) {
F0R (k, alphabets)
c[k] = dp[a][b][k];
}
else if (i == 0) {
F0R (k, alphabets)
c[k] = dp[a][b][k] - dp[a][j-1][k];
}
else if (j == 0) {
F0R (k, alphabets)
c[k] = dp[a][b][k] - dp[i-1][b][k];
}
else {
F0R (k, alphabets) {
c[k] = dp[a][b][k] - (dp[i-1][b][k] + dp[a][j-1][k] - dp[i-1][j-1][k]);
}
}
// print(c);
F0R (k, alphabets) {
if (c[k] <= 0) {
all = false;
break;
}
}
if (all) {
// printf("i=%d, j=%d, a=%d, b=%d, ans += %d\n", i, j, a, b, (n-a)*(max_b-b));
ans += (max_b-b)*(n-a);
max_b = b;
break;
}
}
}
}
}
cout << 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:

input
200
LLLLLLLLLLLLLLLLLHLLLLLLLLLLLL...

correct output
14159445

user output
(empty)

Test 22

Group: 6

Verdict: ACCEPTED

input
500
VVHWVUHVHUWWWVUUUWVUUHUUWHWUVW...

correct output
15683003812

user output
15683003812

Test 23

Group: 6

Verdict:

input
500
OIMZGEQSBMBDSDXSWRFNKSGFEBBTJE...

correct output
15575906951

user output
(empty)

Test 24

Group: 6

Verdict: ACCEPTED

input
500
IIIIIIIIIIIIIIIIIIIIIIIIIIIIII...

correct output
15687562500

user output
15687562500

Test 25

Group: 6

Verdict:

input
500
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWW...

correct output
3058970930

user output
(empty)