比赛 |
USACO铂金组&NOIonline模拟赛 |
评测结果 |
AAAAAAAAAAAAAAA |
题目名称 |
Equilateral Triangles |
最终得分 |
100 |
用户昵称 |
梦那边的美好ET |
运行时间 |
6.577 s |
代码语言 |
C++ |
内存使用 |
14.76 MiB |
提交时间 |
2020-03-03 09:28:35 |
显示代码纯文本
#include<bits/stdc++.h>
#define maxn 310
#define LL long long
using namespace std;
int n,a[maxn][maxn],sum1[maxn][maxn],sum2[maxn][maxn],sum;
char s[maxn];
LL ans;
void solve1(int x,int y,int l){
int p=x-l,q=y-l;
if(p<=0||q<=0||!a[p][y]||!a[x][q])return;
int a1=min(n-x,l),a2=min(n-y,l);
if(a1+a2<l)return;
ans+=(LL)(sum2[x+a1][y+l-a1]-sum2[x+l-a2-1][y+a2+1]);
return;
}
void solve2(int x,int y,int l){
int p=x-l,q=y+l;
if(p<=0||q>n||!a[p][y]||!a[x][q])return;
int a1=min(n-x,l),a2=min(y-1,l);
if(a1+a2<l)return;
ans+=(LL)(sum1[x+a1][y-l+a1]-sum1[x+l-a2-1][y-a2-1]);
return;
}
void solve3(int x,int y,int l){
int p=x+l,q=y+l;
if(p>n||q>n||!a[p][y]||!a[x][q])return;
int a1=min(x-1,l),a2=min(y-1,l);
if(a1+a2<l)return;
ans+=(LL)(sum2[x-l+a2][y-a2]-sum2[x-a1-1][y-l+a1+1]);
return;
}
void solve4(int x,int y,int l){
int p=x+l,q=y-l;
if(p>n||q<0||!a[p][y]||!a[x][q])return;
int a1=min(x-1,l),a2=min(n-y,l);
if(a1+a2<l)return;
ans+=(LL)(sum1[x-l+a2][y+a2]-sum1[x-a1-1][y+l-a1-1]);
return;
}
int main(){
freopen("usaco_Feb_Triangles!.in","r",stdin);
freopen("usaco_Feb_Triangles!.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%s",s+1);
for(int j=1;j<=n;j++)a[i][j]=(s[j]=='*');
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
sum1[i][j]=sum1[i-1][j-1]+a[i][j],
sum2[i][j]=sum2[i-1][j+1]+a[i][j];
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int k=1;k<=n;k++){
solve1(i,j,k);solve2(i,j,k);solve3(i,j,k);solve4(i,j,k);
sum=(i>k&&a[i-k][j])+(j+k<=n&&a[i][j+k])+(i+k<=n&&a[i+k][j])+(j>k&&a[i][j-k]);
ans-=(LL)(sum==3?1:(sum==4?4:0));
}
}
}
printf("%lld\n",ans);
return 0;
}