Submission #1497330
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
//#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned __int128 HASH;
typedef pair<int,int> pii;
typedef pair<ll,int> plli;
typedef pair<int,pii> pipii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;
#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n);i>0;i--)
#define rrep2(i,a,b) for (int i=(a);i>b;i--)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
const ll mod = 1e9 + 7;
const ll hmod1 = 999999937;
const ll hmod2 = 1000000000 + 9;
const ll INF = 1<<30;
const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};
const int dx8[8] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dy8[8] = {0, 1, -1, 1, -1, 0, 1, -1};
const double pi = 3.141592653589793;
const ull B = 1e9 + 7;
int n, m;
vector<string> s(255);
vector<vector<ull>> hs1(255, vector<ull> (255, 0)), hs2(255, vector<ull> (255, 0));
ull power[255];
void constract(vector<string>& s) {
rep(i, n) {
ull tmp = 0;
rep(j, m) {
tmp = tmp * B + s[i][j];
hs1[i][j] = tmp;
}
tmp = 0;
rrep2(j, m - 1, -1) {
tmp = tmp * B + s[i][j];
hs2[i][j] = tmp;
}
}
}
bool match(int top, int btm, int s, int t) {
ull tmp1, tmp2;
if (s == 0) tmp1 = hs1[top][t];
else tmp1 = hs1[top][t] - hs1[top][s - 1] * power[t - s + 1];
if (t == m - 1) tmp2 = hs2[btm][s];
else tmp2 = hs2[btm][s] - hs2[btm][t + 1] * power[t - s + 1];
return tmp1 == tmp2 ? true : false;
}
signed main(){
cin.tie(0);
ios::sync_with_stdio(false);
cin >> n >> m;
power[0] = 1;
rep2(i, 1, m + 1) power[i] = B * power[i - 1];
rep(i, n) cin >> s[i];
constract(s);
ll ans = 0LL;
rep2(i, 1, n) {
rep(j, m - 1) {
int l = j - 1, r = j + 1;
int t = i - 1, b = i;
while (0 <= l && r < m) {
if (!match(t, b, l, r)) break;
ans++;
l--;
r++;
}
if (r - l != 2) {
l++; r--;
t--; b++;
while (0 <= t && b < n) {
if (!match(t, b, l, r)) {
while (l < r && !match(t, b, l, r)) {
l++;
r--;
}
if (l == r) break;
}
ans += r - j;
t--;
b++;
}
}
l = j; r = j + 1;
t = i - 1; b = i;
while (0 <= l && r < m) {
if (!match(t, b, l, r)) break;
ans++;
l--;
r++;
}
if (r - l != 1) {
l++; r--;
t--; b++;
while (0 <= t && b < n) {
if (!match(t, b, l, r)) {
while (l < r && !match(t, b, l, r)) {
l++;
r--;
}
if (r <= l) break;
}
ans += r - j;
t--;
b++;
}
}
}
}
cout << ans << endl;
}
Submission Info
Submission Time |
|
Task |
H - 模様替え |
User |
roto_37 |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
3620 Byte |
Status |
WA |
Exec Time |
113 ms |
Memory |
1408 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Subtask3 |
Score / Max Score |
0 / 0 |
0 / 15 |
0 / 30 |
0 / 55 |
Status |
|
|
|
|
Set Name |
Test Cases |
Sample |
subtask0-sample-01.txt, subtask0-sample-02.txt |
Subtask1 |
subtask0-sample-01.txt, subtask0-sample-02.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt |
Subtask2 |
subtask0-sample-01.txt, subtask0-sample-02.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt |
Subtask3 |
subtask0-sample-01.txt, subtask0-sample-02.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt, subtask3-01.txt, subtask3-02.txt, subtask3-03.txt, subtask3-04.txt, subtask3-05.txt, subtask3-06.txt, subtask3-07.txt, subtask3-08.txt, subtask3-09.txt, subtask3-10.txt, subtask3-11.txt, subtask3-12.txt, subtask3-13.txt, subtask3-14.txt, subtask3-15.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask0-sample-01.txt |
AC |
2 ms |
1280 KB |
subtask0-sample-02.txt |
AC |
2 ms |
1280 KB |
subtask1-01.txt |
AC |
2 ms |
1280 KB |
subtask1-02.txt |
WA |
2 ms |
1280 KB |
subtask1-03.txt |
WA |
2 ms |
1280 KB |
subtask1-04.txt |
AC |
2 ms |
1280 KB |
subtask1-05.txt |
WA |
2 ms |
1280 KB |
subtask1-06.txt |
WA |
2 ms |
1280 KB |
subtask1-07.txt |
AC |
2 ms |
1280 KB |
subtask1-08.txt |
WA |
2 ms |
1280 KB |
subtask1-09.txt |
WA |
2 ms |
1280 KB |
subtask1-10.txt |
WA |
2 ms |
1280 KB |
subtask1-11.txt |
WA |
2 ms |
1280 KB |
subtask1-12.txt |
WA |
2 ms |
1280 KB |
subtask1-13.txt |
WA |
2 ms |
1280 KB |
subtask1-14.txt |
WA |
2 ms |
1280 KB |
subtask1-15.txt |
WA |
2 ms |
1280 KB |
subtask1-16.txt |
AC |
2 ms |
1280 KB |
subtask1-17.txt |
WA |
2 ms |
1280 KB |
subtask1-18.txt |
WA |
2 ms |
1280 KB |
subtask1-19.txt |
WA |
2 ms |
1280 KB |
subtask1-20.txt |
WA |
2 ms |
1280 KB |
subtask2-01.txt |
WA |
2 ms |
1280 KB |
subtask2-02.txt |
WA |
2 ms |
1280 KB |
subtask2-03.txt |
WA |
2 ms |
1280 KB |
subtask2-04.txt |
WA |
2 ms |
1280 KB |
subtask2-05.txt |
WA |
2 ms |
1280 KB |
subtask2-06.txt |
WA |
9 ms |
1280 KB |
subtask2-07.txt |
WA |
2 ms |
1280 KB |
subtask2-08.txt |
WA |
2 ms |
1280 KB |
subtask2-09.txt |
WA |
2 ms |
1280 KB |
subtask2-10.txt |
WA |
8 ms |
1280 KB |
subtask2-11.txt |
WA |
7 ms |
1280 KB |
subtask2-12.txt |
WA |
2 ms |
1280 KB |
subtask2-13.txt |
WA |
8 ms |
1280 KB |
subtask2-14.txt |
WA |
2 ms |
1280 KB |
subtask2-15.txt |
WA |
2 ms |
1280 KB |
subtask3-01.txt |
WA |
2 ms |
1280 KB |
subtask3-02.txt |
WA |
2 ms |
1280 KB |
subtask3-03.txt |
WA |
2 ms |
1280 KB |
subtask3-04.txt |
WA |
2 ms |
1280 KB |
subtask3-05.txt |
WA |
2 ms |
1280 KB |
subtask3-06.txt |
WA |
112 ms |
1408 KB |
subtask3-07.txt |
WA |
17 ms |
1408 KB |
subtask3-08.txt |
WA |
3 ms |
1408 KB |
subtask3-09.txt |
WA |
3 ms |
1408 KB |
subtask3-10.txt |
WA |
3 ms |
1408 KB |
subtask3-11.txt |
WA |
3 ms |
1408 KB |
subtask3-12.txt |
WA |
3 ms |
1408 KB |
subtask3-13.txt |
WA |
113 ms |
1408 KB |
subtask3-14.txt |
WA |
3 ms |
1408 KB |
subtask3-15.txt |
WA |
3 ms |
1408 KB |