A組
題目
矮人排隊
Time Limits: 1000 ms
Memory Limits: 32768 KB
Description
在七山七海之外的一個小村莊，白雪公主與N個矮人住在一起，所有時間都花在吃和玩League of Legend遊戲。白雪公主決心終結這樣的生活，是以為他們舉辦了體育課。 在每節課開始時，矮人必須按他們的身高站隊。假定矮人們有高度1，2，…，N（每個人高度互不相同）。然而，由于不健康的生活方式，矮人的智力有所惡化，是以他們沒有能力依照自己的高度排序。
是以，白雪公主發出以下形式指令幫助他們：
1 X Y：X和Y位置的矮人互換位置。
2 A B：詢問高度為A，A+1，…， B的矮人（不一定是按照這個順序）是否已形成了目前隊列的連續子序列。
幫助矮人按照白雪公主的訓示行動，并回答她的問題。
Input
輸入的第一行包含兩個正整數N和M，分别表示矮人的數量和白雪公主的指令數，2≤N≤200,000，2≤M≤200,000。
第二行包含N個用空格隔開的從1到N的正整數，每個數隻出現一次，代表矮人的初始排列。
接下來的M行包含白雪公主的指令，形式為“1 X Y”（1≤X，Y≤N，X≠Y）或“2 A B”（1≤A≤B≤N）。
Output
對于每個指令2輸出“YES”或“NO”。
Sample Input
輸入1：
5 3
2 4 1 3 5
2 2 5
1 3 1
2 2 5
輸入2：
7 7
4 7 3 5 1 2 6
2 1 7
1 3 7
2 4 6
2 4 7
2 1 4
1 1 4
2 1 4
Sample Output
輸出1：
NO
YES
輸出2：
YES
NO
YES
NO
YES
Data Constraint
50%的資料：類型2詢問中A,B滿足 B − A ≤ 50 B-A≤50 B−A≤50
間諜派遣
Time Limits: 1000 ms
Memory Limits: 32768 KB
Description
你是M，一個雇傭N個标号為從1到N的間諜的情報機關的總管。每個間諜被派往不同的國家并在那擷取重要情報。
如下是你的任務：
- 在部分間諜間組織會面。每次會面在兩個間諜間進行，兩個間諜交換他們自己擷取的或從之前會面中得到的資訊。因為在不同國家的兩個間諜間組織機密會面很困難，是以每次秘密會面都有一個費用。
- 當所有會面結束後，選擇一部分間諜參加拯救世界的任務。一個間諜k參加此項任務需要花費Mk。很重要的一點是，任務要成功，必須滿足參加任務的間諜擷取的情報聚集到一起包含了其他剩餘間諜所有的資訊。
請找出完成任務的最小花費，即組織會面和派遣間諜的費用之和。
Input
輸入的第一行包含正整數N，表示間諜數目（ 2 ≤ N ≤ 1000 2≤N≤1000 2≤N≤1000）。
接下來的N行包含N個不超過 1 0 6 10^6 106的非負整數。在k行m列的數字表示間諜k和m間會面的花費，同樣的，與m行k列的數字相等，k=m時數字為0。
接下來的一行包含N個正整數 M k M_k Mk（ 1 ≤ M k ≤ 1 0 6 1≤M_k≤10^6 1≤Mk≤106），分别為派遣間諜1，2，…，N參加任務的花費。
Output
隻有一行，為所需的最小總費用。
Sample Input
輸入1：
3
0 6 9
6 0 4
9 4 0
7 7 7
輸入2：
3
0 17 20
17 0 10
20 10 0
15 9 12
輸入3：
5
0 3 12 15 11
3 0 14 3 20
12 14 0 11 7
15 3 11 0 15
11 20 7 15 0
5 10 10 10 10
Sample Output
輸出1：
17
輸出2：
34
輸出3：
28
Data Constraint
40%的資料滿足N<=30且存在最多不超過4個間諜參加任務的最優方案;
50%的資料滿足派遣每個間諜參加任務的費用是一樣的。
Hint
樣例1：将會在1和2，接着2和3間諜間舉行會面，然後送間諜2參與任務。
樣例2：将會在2和3間諜間舉行會面，然後送間諜1和2參與任務。
樣例3：将會在2和4，接着1和2，接着3和5間諜間舉行會面，然後送間諜1和3（或1和5）參與任務。
逾時空旅行
Special Judge
Test 0 1000 ms 32768 KB
Test 1 1000 ms 32768 KB
Test 2 1000 ms 32768 KB
Test 3 1000 ms 32768 KB
Test 4 1000 ms 32768 KB
Test 5 5000 ms 32768 KB
Test 6 1000 ms 32768 KB
Test 7 1000 ms 32768 KB
Test 8 1000 ms 32768 KB
Test 9 5000 ms 32768 KB
Description
在遙遠的未來，行星之間的食品運輸将依靠單向的貿易路線。每條路徑直接連接配接兩個行星，且其運輸時間是已知的。
貿易商協會打算利用一項最近發現的新技術——超空間旅行，以增加一些新的航線。通過超空間旅行的航線也是單向的。由于該項技術仍處于試驗階段，超空間旅行的時間目前是未知的，但它不取決于行星之間的距離，是以每個超空間旅行的路線将花費等量的時間。
下圖是三個互相聯通的行星及其運輸時間的例子。行星使用正整數标号，超空間旅行時間記為“x”（圖檔對應第二個輸入樣例）：
運輸時間以天計，并且始終是一個正整數。
貿易商協會希望對引進新航線的結果進行分析：對于某兩個行星A和B，他們想知道對于任意的x，從A到B的最短路徑的總運輸時間的所有可能的值。例如，在上述情況中，從星球2到星球1的最短路徑所需時間可以取值5（如果x≥5），4，3，2，或1天（如果x<5）
Input
輸入的第一行包含兩個整數P和R，分别代表行星的數目和航線數量，1≤P≤500，0≤R≤10000。
接下來的R條航線路徑包含兩或三個整數：行星标号C和D（1≤C，D≤P，C≠D），和T，從C到D的旅行時間。對于傳統的路徑，T是一個整數（1≤T≤1000000），超空間航線中，T是字元“x”。 可以存在多行有兩個相同的行星。
下一行輸入整數Q（1≤Q≤10），表示查詢的數量。
以下Q行包含兩個整數星球标号（A和B，A≠B），為貿易商協會的查詢：“從A到B的最短路徑時間的可能值是什麼？
Output
輸出必須包含Q行。
每一行都必須包含兩個整數：不同的可能值的數目和它們的總和。如果不同的可能值的數目是無限的，該行隻輸出“inf”。如果不存在從A到B的路徑，不同的可能值的數目及它們的總和都是0。
Sample Input
輸入1：
4 4
1 2 x
2 3 x
3 4 x
1 4 8
3
2 1
1 3
1 4
輸入2：
3 5
3 2 x
2 1 x
2 1 5
1 3 10
3 1 20
6
1 2
2 3
3 1
2 1
3 2
1 3
Sample Output
輸出1：
0 0
inf
3 17
輸出2：
inf
5 65
15 185
5 15
inf
1 10
Data Constraint
50%的資料滿足 P ≤ 30 , R ≤ 300 , T ≤ 50 P≤30, R≤300, T≤50 P≤30,R≤300,T≤50。
如果一個詢問的結果不是“inf”，則你的輸出必須輸出兩個數，否則不得分；如果所有詢問的第一問正确可以得一半分。
Hint
樣例 1解釋：
- 從2到1不存在可能的路徑。
- 對于任意正整數x，從1到3的最短路徑花費的時間是2x，是以答案是“inf”。
- 從1到4的最短路徑可以花費3（當x=1），6（當x=2），或8（當x≥3）的時間，3+6+8=17
2019.07.11【NOIP提高組】模拟 A 組&B組總結A組總結CODE
B組題目
照片
Time Limits: 1000 ms
Memory Limits: 131072 KB
Description
Farmer John決定為他的N頭排列好的奶牛（1 <= N<= 200,000）做一張全景合照。這N頭奶牛分别以1…N進行編号。他一共拍了M（1<= M <=100,000）張相片，每張相片都隻包含有一部分位置連續的奶牛：第i張照片涵蓋着編号從a_i到b_i的所有奶牛。當然，這些照片合起來并不保證包含所有的牛。
Farmer John拍攝完所有的相片後，注意到一個很有趣的現象：他拍的每張照片中有且僅有一隻奶牛身上有斑點。 FJ知道他的奶牛中有一部分是身上有斑點的，但他從來沒有數過這種奶牛的數目。請根據FJ的這些照片，确定可能出現的斑點牛的最大的數目；若從FJ的照片中無法推測斑點牛的數目，則輸出-1。
Input
第1行：包含兩個整數N、M。
第2… M+1… i +1行：每行包含兩個整數a_i和b_i。
Output
輸出僅一行，要求輸出FJ根據他的照片所能推測出的斑點牛的最大數目；若無法推測這些奶牛的數目，則輸出-1。
Sample Input
5 3
1 4
2 5
3 4
Sample Output
1
Data Constraint
1 ≤ N ≤ 200 , 000 1\leq N\leq 200,000 1≤N≤200,000
陰陽
Time Limits: 1000 ms
Memory Limits: 131072 KB
Description
Farmer John 正在在計劃自己的農場漫步。他的農場的結構就像一棵樹：農場有N個谷倉（1<= N <=100,000），分别由N-1條路連結。這樣，他便可以通過這些谷倉間的道路遍及各個谷倉。Farmer John想要選擇一條路線：這條路線的起點和終點分别為農場中兩個不同的谷倉，這條路線不能重複經過一條邊兩次。Farmer John擔心這條路徑可能會偏長，是以他想在路線上尋找一個休息點（當然這個休息點不能為起點或者終點）。
每條邊的兩旁都是牛群，要麼是Charcolais（白毛），要麼是Angus（黑毛）。Farmer John是一個聰明人，是以他想要在他通過小路的同時平衡小路兩側陰陽的力量。他要選擇一條路徑使得他從起點到休息站，和從休息站到終點這兩段路上都滿足路兩邊的Charcolais牛群和Angus牛群總數量相同。
Farmer John好奇他能找到多少條如上所述的平衡的路徑。我們認為，當且僅當兩條路線的邊的集合不同時，這兩條路徑才被認為是不同的，否則認為是相同的路線。就算路線上有多個有效的“休息站”的位置能使路線平衡，我們也隻記為一條路線。
請幫助計算有多少條不同的平衡路線。
Input
第1行：包含一個整數N。
第2… N行：每行包含三個整數a_i、b_i和t_i，表示第i條路徑連接配接的兩個谷倉a_i、b_i。t_i表示第i條路邊上的牛群種類：0表示Charcolais，1表示Angus。
Output
輸出僅一行，包含一個整數，表示可能存在的路徑數目。
Sample Input
7
1 2 0
3 1 1
2 4 0
5 2 0
6 3 1
5 7 1
Sample Output
1
Data Constraint
1 ≤ N ≤ 100 , 000 1\leq N\leq 100,000 1≤N≤100,000
Hint
不存在長度為2的路線，是以我們隻能考慮長度為4的路線，路線3-1-2-5-7休息點設在2是一條平衡路線。
數字八
Time Limits: 1000 ms
Memory Limits: 131072 KB
Description
Farmer John的奶牛最近收到一塊大理石。但不幸的是，這塊石頭有些不完整。為了說明這塊石頭的狀況，我們就可以用一個N* N正方形網格（5 <= N <=300）來描述，其中字元’*‘代表石頭的缺損部分，’.'表示石頭完美無瑕的部分。
奶牛要在這一塊大理石上雕刻數字“8”。然而，牛也需要FJ的幫助，以确定在這塊大理石上最佳的雕刻位置。這裡有幾個要求來定義一個有效的數字8：
*數字8由上下兩個矩形構成。
*數字8的上下兩個矩形都滿足至少有一個單元格在矩形内部，也就是說兩個矩形都至少是3 *3的。
*數字8頂部的矩形的底邊必須為底部矩形頂邊的子集。
*數字8隻能刻在大理石完美無瑕的部分。
*規定數字8的得分為上矩形和下矩形的面積的乘積。
請确定奶牛所能構造的最大數字8.
Input
第1行：包含一個整數N，表示大理石的邊長。
第2… N+1行：第行描述的是大理石的第i-1行的狀态，包含N個字元。其中字元’*‘代表石頭的缺損部分，’.'表示石頭完美無瑕的部分
Output
輸出僅一行，包含一個整數，表示所能得到的最大的數字8得分。
Sample Input
15
...............
...............
...*******.....
.*....*.......*
.*......*....*.
....*..........
...*...****....
...............
..**.*..*..*...
...*...**.*....
*..*...*.......
...............
.....*..*......
.........*.....
...............
Sample Output
3888
Data Constraint
5 < = N < = 300 5 <= N <=300 5<=N<=300
Hint
上面的矩形面積為69=54，下面的矩形面積為126，得分為54*72=3888
總結
A組
今天的比賽是放反了吧！
往年的比賽（它們在同一個模拟賽）：
于是今天A組的大衆分200，B組的大衆分50。
A組T1很顯然是權值線段樹，維護一下每一段數字中最前的位置和最後的位置，然後每次判斷一下詢問區間中數字排列的前後跨度是否等于數字差即可。
T2也很顯然，是最小生成樹，可以建立一個節點S，把S和每一個間諜 i 連一條值為 M i M_i Mi的邊，間諜 i 和間諜 j 中間連一條費用為 i,j 會面花費的邊。這是很容易想的。
T3比賽時想錯了，維護了走x和不走x的2個最短路，結果還打錯了。。。
其實T3要維護所有數量的x的情況，然後就得到了很多條路線，其中第 i 條可以視作 k x + b kx+b kx+b，其中k是x邊的數量，b是非x邊之和。
這是不是很眼熟呢？把設x的值為x軸，長度為y軸，那麼我們就可以畫出一堆直線，顯然最優答案會組成一個上凸殼，用類似于斜率優化的方法搞就可以了。
那麼水的題目，我竟然沒有AK，太不應該了。
B組
從某個同學的總結就可以看出今天的B組有多麼 ∗ ∗ ** ∗∗。
T1設 f i f_i fi表示在 i 放一隻斑點奶牛時，斑點奶牛的最多數量， l i l_i li表示在 i 放了以後前面最遠在哪裡必須放上一隻奶牛， r i r_i ri表示在 i 放了以後前面最近在哪裡可以放上一隻奶牛。
一通亂搞即可。
T2點分治，不會。
T3
可以先處理上半個矩形，在處理下半個矩形。
考慮下面這個圖形
其中藍色部分是目前處理到的上部分，可以設 f i , j , k f_{i,j,k} fi,j,k表示目前處理到的矩形左邊界為 i ，右邊界為 j ，下邊界為k，則
f i , j , k = max { − 1 , 第(k,i)或(k,j)個格子破損 f i , j , k − 1 + 1 , f i , j , k − 1 ≠ − 1 0 從(k,i)到(k,j)無破損 f_{i,j,k}=\max\begin{cases} -1,&\text{第(k,i)或(k,j)個格子破損}\\ f_{i,j,k-1}+1,&f_{i,j,k-1}\neq-1\\ 0&\text{從(k,i)到(k,j)無破損} \end{cases} fi,j,k=max⎩⎪⎨⎪⎧−1,fi,j,k−1+1,0第(k,i)或(k,j)個格子破損fi,j,k−1̸=−1從(k,i)到(k,j)無破損
用 s i , j , k s_{i,j,k} si,j,k表示此時的面積，則 s i , j , k = ( j − i − 1 ) × ( f i , j , k − 2 ) s_{i,j,k}=(j-i-1)\times(f_{i,j,k}-2) si,j,k=(j−i−1)×(fi,j,k−2)
然後判斷一下如果一個大矩形包含一個小矩形，那麼用小矩形的面積更新大矩形的面積。
接着倒過來做，合并一下上下矩形就好了。
CODE
A組
T1
#include<cstdio>
using namespace std;
#define N 200005
#define M 1000005
#define lson k<<1
#define rson k<<1|1
char ch;
inline char gc()
{
static char buf[M],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,N,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x)
{
while(ch=gc(),ch<'0'||ch>'9');x=ch-'0';
while(ch=gc(),ch>='0'&&ch<='9') x=x*10+ch-'0';
}
int max[N*18],min[N*18],a[N],maxx,minn;
inline int mymax(int x,int y){return x>y?x:y;}
inline int mymin(int x,int y){return x<y?x:y;}
inline void update(int k)
{
if(max[lson]>max[rson]) max[k]=max[lson];
else max[k]=max[rson];
if(min[lson]<min[rson]) min[k]=min[lson];
else min[k]=min[rson];
}
void change(int k,int l,int r,int id,int num)
{
if(l==r)
{
max[k]=min[k]=num;
return;
}
int mid=l+r>>1;
if(id<=mid) change(lson,l,mid,id,num);
else change(rson,mid+1,r,id,num);
update(k);
}
void qry(int k,int l,int r,int x,int y)
{
if(l==x&&r==y)
maxx=mymax(maxx,max[k]),
minn=mymin(minn,min[k]);
else
{
int mid=l+r>>1;
if(y<=mid) qry(lson,l,mid,x,y);
else if(x>mid) qry(rson,mid+1,r,x,y);
else qry(lson,l,mid,x,mid),qry(rson,mid+1,r,mid+1,y);
}
}
/*void print(int k,int l,int r)
{
printf("%d\t%d\t%d\t%d\t%d\n",k,l,r,min[k],max[k]);
if(l==r) return;
int mid=l+r>>1;
print(lson,l,mid);
print(rson,mid+1,r);
}*/
int main()
{
int n,m,i,x,y;
read(n),read(m);
for(i=1;i<=n;i++)
read(a[i]),change(1,1,n,a[i],i);
//print(1,1,n);
while(m--)
{
read(i),read(x),read(y);
if(i==1)
change(1,1,n,a[x],y),
change(1,1,n,a[y],x),
a[x]^=a[y],a[y]^=a[x],a[x]^=a[y];
else
maxx=0,minn=N,
qry(1,1,n,x,y),
puts(maxx-minn==y-x?"YES":"NO");
}
return 0;
}
T2
//I saw a spy,fly in the sky,eat a pie,with a knife,and a kite.I asked him why,he said he'll die,because of the flies,so he fly,with a kite.
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 1005
#define M 501005
struct edge
{
int start,end,lenth;
}a[M];
int f[N],m,ans;char ch;
inline char gc()
{
static char buf[M],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,N,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x)
{
while(ch=gc(),ch<'0'||ch>'9');x=ch-'0';
while(ch=gc(),ch>='0'&&ch<='9') x=x*10+ch-'0';
}
bool cmp(edge x,edge y){return x.lenth<y.lenth;}
inline int getfather(int k)
{
if(f[k]==k) return k;
return f[k]=getfather(f[k]);
}
inline void build()
{
sort(a+1,a+m+1,cmp);
int i,x,y;
for(i=1;i<=m;i++)
{
x=a[i].start,y=a[i].end;
if(getfather(x)!=getfather(y))
{
f[f[x]]=f[y];
ans+=a[i].lenth;
}
}
}
int main()
{
int n,i,j,k;
read(n),n++;
for(i=1;i<n;i++)
for(j=1;j<n;j++)
{
read(k);
if(i<j) a[++m]=(edge){i,j,k};
}
for(i=1;i<n;i++) read(k),a[++m]=(edge){n,i,k},f[i]=i;
f[n]=n,build();
printf("%d\n",ans);
return 0;
}
T3
#include<cstdio>
#include<queue>
using namespace std;
#define ll long long
#define inf 999999999
#define M 10005
#define N 505
struct edge{int end,lenth,next;}a[M<<1];
struct node{int x,y;}temp;
struct line{ll k,b;}num[M],stack[M];
queue<node>data;
int fir[N],dis[N][N],n,m,i,j,s;
bool exist[N][M];char ch;
inline char gc()
{
static char buf[1000005],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,N,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x)
{
while(ch=gc(),ch!='x'&&(ch<'0'||ch>'9'));
if(ch=='x'){x=0;return;}
x=ch-'0';
while(ch=gc(),ch>='0'&&ch<='9') x=x*10+ch-'0';
}
inline void inc(int x,int y,int z)
{a[++s]=(edge){y,z,fir[x]},fir[x]=s;}
inline void spfa(int st)
{
int x,y,u;
for(i=1;i<=n;i++)
for(j=0;j<=n;j++)
dis[i][j]=inf,exist[i][j]=1;
data.push((node){st,0}),dis[st][0]=0;
while(!data.empty())
{
temp=data.front(),data.pop();
x=temp.x,y=temp.y,exist[x][y]=1;
for(i=fir[x];i;i=a[i].next)
{
u=a[i].end;
if(a[i].lenth)
{
if(dis[u][y]>dis[x][y]+a[i].lenth)
{
dis[u][y]=dis[x][y]+a[i].lenth;
if(exist[u][y]) exist[u][y]=0,data.push((node){u,y});
}
}
else if(dis[u][y+1]>dis[x][y])
{
dis[u][y+1]=dis[x][y];
if(exist[u][y+1]) exist[u][y+1]=0,data.push((node){u,y+1});
}
}
}
}
inline double crossing(line u,line v)
{return (v.b-u.b+0.0)/(double)(u.k-v.k);}
inline ll count(ll x,ll y)
{return (x+y)*(y-x+1)>>1;}
int main()
{
int q,i,j,x,y,z,last,now,top;
ll sum;bool no;
read(n),read(m);
for(i=1;i<=m;i++)
{
read(x),read(y),read(z);
inc(x,y,z);
}
read(q);
while(q--)
{
read(x),read(y),spfa(x);
if(dis[y][0]==inf)
{
for(i=1,no=1;i<=n;i++)
if(dis[y][i]<inf){no=0;break;}
if(no) puts("0 0");else puts("inf");
continue;
}
for(i=n,top=0;i>=0;i--)
{
num[i]=(line){i,dis[y][i]};
if(i&&dis[y][i]>=dis[y][i-1]) continue;
while(top>1&&crossing(stack[top-1],stack[top])>crossing(stack[top],num[i])) top--;
while(top&&stack[top].b>dis[y][i]) top--;
stack[++top]=num[i];
}
if(top==1){printf("1 %lld\n",stack[1].b);continue;}
for(i=1,last=1,sum=0;i<top;last=now+1,i++)
{
now=crossing(stack[i],stack[i+1]);
if(last<=now)
sum+=1LL*count(last,now)*stack[i].k+1LL*(now-last+1)*stack[i].b;
}
if(crossing(stack[top-1],stack[top])>now) now++,sum+=stack[top].b;
printf("%d %lld\n",now,sum);
}
return 0;
}
B組
T1
#include<cstdio>
using namespace std;
#define N 200005
int f[N],l[N],r[N],queue[N];
inline int min(int x,int y){return x<y?x:y;}
inline int max(int x,int y){return x>y?x:y;}
int main()
{
int n,m,i,j,a,b,head=1,tail=1;
scanf("%d%d",&n,&m);
for(i=1;i<=n+1;i++) r[i]=i-1;
for(i=1;i<=m;i++)
scanf("%d%d",&a,&b),
l[b+1]=max(l[b+1],a),
r[b]=min(r[b],a-1);
for(i=2;i<=n+1;i++) l[i]=max(l[i-1],l[i]);
for(i=n;i>0;i--) r[i]=min(r[i+1],r[i]);
for(i=j=1;i<=n+1;i++)
{
for(;j<=r[i];j++)
{
if(f[j]>-1)
{
while(head<=tail&&f[queue[tail]]<f[j]) tail--;
queue[++tail]=j;
}
}
while(head<=tail&&queue[head]<l[i]) head++;
if(head>tail) f[i]=-1;
else if(i<=n) f[i]=f[queue[head]]+1;
else f[i]=f[queue[head]];
}
printf("%d\n",f[n+1]);
return 0;
}
T3
#include<cstdio>
#include<cstring>
using namespace std;
#define N 305
inline char gc()
{
static char buf[200005],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,N,stdin),p1==p2)?EOF:*p1++;
}
short f[2][N][N],sum[N][N];
int s[N][N][N];
bool a[N][N];char ch;
inline void readint(int &x)
{
while(ch=gc(),ch<'0'||ch>'9');x=ch-'0';
while(ch=gc(),ch>='0'&&ch<='9') x=x*10+ch-'0';
}
inline void readchar(){while(ch=gc(),ch!='.'&&ch!='*');}
inline int max(int x,int y){return x>y?x:y;}
inline bool judge(int k,int i,int j){return sum[k][j]-sum[k][i-1]==0;}//(k,i) to (k,j)
int main()
{
int n,i,j,k,t,now,las,ans=0;
readint(n);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
readchar(),a[i][j]=(ch=='*'),
sum[i][j]=sum[i][j-1]+a[i][j];
memset(f[0],-1,sizeof(f[0]));
for(k=now=1,las=0;k<=n;k++,now^=1,las^=1)
{
memset(f[now],-1,sizeof(f[now]));
for(i=1;i<n;i++)
{
for(j=i+1;j<=n;j++)
{
if(a[k][i]||a[k][j]) continue;
if(f[las][i][j]>-1) f[now][i][j]=f[las][i][j]+1;
else if(judge(k,i,j)) f[now][i][j]=0;
if(f[now][i][j]>2&&j>i+1)
{
s[k][i][j]=(j-i-1)*(f[now][i][j]-1);
}
}
}
}
for(k=1;k<=n;k++)
for(i=3;i<n;i++)
for(j=1;j<=n-i;j++)
s[k][j][j+i]=max(s[k][j][j+i],max(s[k][j+1][j+i],s[k][j][j+i-1]));
memset(f[las],-1,sizeof(f[las]));
for(k=n;k>0;k--,now^=1,las^=1)
{
memset(f[now],-1,sizeof(f[now]));
for(i=1;i<n;i++)
{
for(j=i+1;j<=n;j++)
{
if(a[k][i]||a[k][j]) continue;
if(f[las][i][j]>-1) f[now][i][j]=f[las][i][j]+1;
else if(judge(k,i,j)) f[now][i][j]=0;
if(f[now][i][j]>2&&j>i+1&&judge(k,i,j))
{
ans=max(ans,(j-i-1)*(f[now][i][j]-1)*s[k][i][j]);
}
}
}
}
if(!ans) ans=-1;
printf("%d\n",ans);
return 0;
}