Submission #309641
Source Code Expand
// #define _CRT_SECURE_NO_WARNINGS
// #define _USE_MATH_DEFINES
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <cstdlib>
#include <functional>
#include <locale>
#include <cctype>
#include <sstream>
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef map<int, int> MAPII;
typedef multimap<int, char, greater<int> > MuMAPIC;
typedef vector<pair<int, int> > VPII;
typedef multimap<int, string, greater<int> > MuMIS;
#define MP make_pair
#define fastIO cin.tie(0); ios::sync_with_stdio(false);
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define foreach_it(type,it,c) for(type::iterator it=c.begin(),c_end=c.end();it!=c_end;++it)
#define DUMP_VVI(b) FOR(i,0,b.size()){FOR(j,0,b[i].size())printf("%d ",b[i][j]);puts("");}
// 入力をpush_back(d)やarray[d]に使う時に1行で書ける
// int INPUT_INT() {int d;cin>>d;return d;}
template<class T>T IN(){T d;cin>>d;return d;}
// -------------------- include, typedef, define, template END. --------------------
string inline SubString(int r, int HU_c, int MS_c, int revFlag, vector<string> &field){
string temp = field[r].substr(HU_c, MS_c-HU_c+1);
if(revFlag)
reverse(temp.begin(),temp.end());
return temp;
}
int inline solve2(int R, int C, vector<string> &field){
int ans=0;
string temp1,temp2;
// HU : 左上, MS : 右下, dis : distance from the center line.
FOR(HU_c,0,C-1){
FOR(MS_c,HU_c+1,C){
// 高さが奇数(1,3,5,...)の四角形
FOR(i,0,R){
// 中央1行チェック
if(SubString(i,HU_c,MS_c,0,field) != SubString(i,HU_c,MS_c,1,field))
continue; // 次のiへ.
for(int dis=1; i-dis>=0 && i+dis<R; dis++){
// 今見る四角形(最上行i-dis, 最下行i+dis)が, fieldに収まっているなら実行.
if(SubString(i-dis,HU_c,MS_c,0,field) == SubString(i+dis,HU_c,MS_c,1,field))
ans++;
else
break;
}
}
// 高さが偶数(2,4,6,...)の四角形
FOR(i,0,R){
for(int dis=1; i-dis+1>=0 && i+dis<R; dis++){
// 今見る四角形(最上行i-dis+1, 最下行i+dis)が, fieldに収まっているなら実行.
if(SubString(i-dis+1,HU_c,MS_c,0,field) == SubString(i+dis,HU_c,MS_c,1,field))
ans++;
else
break;
}
}
}
}
return ans;
}
// 以下のURL先のコードに大変お世話になりました.
// http://code-thanks-festival-2014-a-open.contest.atcoder.jp/submissions/294369
// 解法:4重ループにする,ローリングハッシュを書く.
int main(){
fastIO;
int R = 0, C = 0;
cin >> R >> C;
vector<string> field;
field.reserve(R);
FOR(i,0,R)
field.push_back(IN<string>());
cout << solve2(R, C, field) << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
H - 模様替え |
User |
conchan_akita |
Language |
C++ (G++ 4.6.4) |
Score |
45 |
Code Size |
2887 Byte |
Status |
TLE |
Exec Time |
8035 ms |
Memory |
1124 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Subtask3 |
Score / Max Score |
0 / 0 |
15 / 15 |
30 / 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 |
26 ms |
920 KB |
subtask0-sample-02.txt |
AC |
28 ms |
956 KB |
subtask1-01.txt |
AC |
28 ms |
860 KB |
subtask1-02.txt |
AC |
28 ms |
856 KB |
subtask1-03.txt |
AC |
28 ms |
912 KB |
subtask1-04.txt |
AC |
29 ms |
908 KB |
subtask1-05.txt |
AC |
38 ms |
920 KB |
subtask1-06.txt |
AC |
33 ms |
924 KB |
subtask1-07.txt |
AC |
27 ms |
916 KB |
subtask1-08.txt |
AC |
27 ms |
916 KB |
subtask1-09.txt |
AC |
32 ms |
920 KB |
subtask1-10.txt |
AC |
31 ms |
916 KB |
subtask1-11.txt |
AC |
27 ms |
912 KB |
subtask1-12.txt |
AC |
28 ms |
916 KB |
subtask1-13.txt |
AC |
37 ms |
912 KB |
subtask1-14.txt |
AC |
29 ms |
920 KB |
subtask1-15.txt |
AC |
27 ms |
920 KB |
subtask1-16.txt |
AC |
31 ms |
920 KB |
subtask1-17.txt |
AC |
31 ms |
920 KB |
subtask1-18.txt |
AC |
30 ms |
920 KB |
subtask1-19.txt |
AC |
29 ms |
856 KB |
subtask1-20.txt |
AC |
31 ms |
916 KB |
subtask2-01.txt |
AC |
109 ms |
916 KB |
subtask2-02.txt |
AC |
109 ms |
852 KB |
subtask2-03.txt |
AC |
157 ms |
912 KB |
subtask2-04.txt |
AC |
256 ms |
916 KB |
subtask2-05.txt |
AC |
245 ms |
988 KB |
subtask2-06.txt |
AC |
3631 ms |
984 KB |
subtask2-07.txt |
AC |
254 ms |
920 KB |
subtask2-08.txt |
AC |
255 ms |
916 KB |
subtask2-09.txt |
AC |
253 ms |
916 KB |
subtask2-10.txt |
AC |
3965 ms |
916 KB |
subtask2-11.txt |
AC |
5172 ms |
864 KB |
subtask2-12.txt |
AC |
256 ms |
912 KB |
subtask2-13.txt |
AC |
4021 ms |
864 KB |
subtask2-14.txt |
AC |
247 ms |
868 KB |
subtask2-15.txt |
AC |
259 ms |
976 KB |
subtask3-01.txt |
AC |
200 ms |
904 KB |
subtask3-02.txt |
AC |
891 ms |
928 KB |
subtask3-03.txt |
AC |
543 ms |
980 KB |
subtask3-04.txt |
AC |
605 ms |
864 KB |
subtask3-05.txt |
AC |
545 ms |
872 KB |
subtask3-06.txt |
TLE |
8033 ms |
1112 KB |
subtask3-07.txt |
AC |
6047 ms |
1036 KB |
subtask3-08.txt |
AC |
4987 ms |
1040 KB |
subtask3-09.txt |
AC |
4866 ms |
936 KB |
subtask3-10.txt |
AC |
4873 ms |
992 KB |
subtask3-11.txt |
AC |
4789 ms |
1000 KB |
subtask3-12.txt |
AC |
4894 ms |
976 KB |
subtask3-13.txt |
TLE |
8035 ms |
1124 KB |
subtask3-14.txt |
AC |
4861 ms |
1004 KB |
subtask3-15.txt |
AC |
4914 ms |
984 KB |