A. Drone With a Camera

三分套三分。

#include
     
      #include
      
       #include
       
        using namespace std;typedef long double ld;const ld K=1e9,inf=1e100,eps=1e-9;const int T=200;struct P{  ld x,y;  P(){}  P(ld _x,ld _y){x=_x,y=_y;}}O;struct Line{  ld a,b,c;  void init(){    double _a,_b,_c;    scanf("%lf%lf%lf",&_a,&_b,&_c);    a=_a,b=_b,c=_c;  }  P cal(ld x){    if(fabs(b)>fabs(a))return P(x,(c-a*x)/b);    return P((c-b*x)/a,x);  }}A,B;inline ld sqr(ld x){return x*x;}inline ld dis(P a,P b){  return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}inline ld cal(ld x,ld y){  P u=A.cal(x);  P v=B.cal(y);  return dis(O,u)+dis(u,v)+dis(v,O);}inline ld ASK(ld x){  ld l=-K,r=K,ans=inf;  for(int i=T;i--;){    ld len=(r-l)/3;    ld m1=l+len,m2=r-len;    ld f1=cal(x,m1),f2=cal(x,m2);    ans=min(ans,min(f1,f2));    if(f1
       
      
     

　　

B. Fibonaccis’ vouchers

考虑用最少的Fib数表示一个数，只需要从大到小贪心选取每个Fib数。

将一个数写成Fib进制，可以得到一个$01$串，满足没有连续两个$1$。

从高位到低位逐位确定答案的每一位是$0$还是$1$，需要求出在给定前缀的情况下，有多少个$01$字符串满足没有连续两个$1$，且$1$的个数不超过$k$。设$f[i][j][k]$表示考虑了前$i$位，一共$j$个$1$，第$i$位是$k$的字符串的方案数，DP统计即可。

时间复杂度$O(k^3)$。

#include
     
      typedef long long ll;const ll inf=1000000000000000000LL;const int N=150;int cnt,i,j,k,b[N];ll a[N],n,ans;ll f[N][N][2];inline ll add(ll a,ll b){  a+=b;  if(a>inf+10)return inf+10;  return a;}inline int cal(ll x){  int ret=0;  for(int i=cnt;i;i--)if(x>=a[i])x-=a[i],ret++;  return ret;}inline ll solution(int lim){  //[1..lim] are not known  int i,j,x,o;  for(i=0;i<=cnt+10;i++)for(j=0;j<=k;j++)for(o=0;o<2;o++)f[i][j][o]=0;  int _=0;  for(i=lim+1;i<=cnt;i++)if(b[i]&&b[i+1])return 0;  for(i=lim+1;i<=cnt;i++)_+=b[i];  if(_>k)return 0;  f[lim+1][_][b[lim+1]]=1;  for(i=lim+1;i>1;i--)for(j=0;j<=k;j++)for(o=0;o<2;o++)for(x=0;x<2;x++){    if(o&&x)continue;    if(j+x>k)continue;    f[i-1][j+x][x]=add(f[i-1][j+x][x],f[i][j][o]);  }  ll ret=0;  for(j=0;j<=k;j++)for(o=0;o<2;o++)ret=add(ret,f[1][j][o]);  return ret;}int main(){  a[1]=1;  a[2]=2;  for(i=3;;i++){    a[i]=a[i-1]+a[i-2];    if(a[i]<=inf)cnt=i;    else break;  }  //it should >= k  scanf("%d%lld",&k,&n);  for(i=0;i
      
       <=k)n++;  for(i=cnt;i;i--){    for(j=0;j<2;j++){      b[i]=j;      ll tmp=solution(i-1);      //printf("%d %d %lld\n",i,j,tmp);      if(n<=tmp)break;      else{        n-=tmp;      }    }    if(j==2)return puts("NIE"),0;  }  for(i=1;i<=cnt;i++)if(b[i])ans=add(ans,a[i]);  if(ans>inf)puts("NIE");else printf("%lld",ans);}
      
     

　　

C. Chinese Remainder Theorem

对于一个式子$a_i\equiv b_i\pmod{m}(a_i\geq b_i)$，$m$需要满足$m|a_i-b_i$，所以$m$的最大值为$\gcd(a_i-b_i)$。

#include
     
      typedef long long ll;int n,i;ll ans,a[111111],b[111111];ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}int main(){  scanf("%d",&n);  for(i=1;i<=n;i++)scanf("%lld",&a[i]);  for(i=1;i<=n;i++)scanf("%lld",&b[i]);  for(i=1;i<=n;i++)ans=gcd(ans,a[i]-b[i]);  printf("%lld",ans);}
     

　　

D. Road

因为下雪操作是全局操作，因此最厚的位置一定是最后一次扫雪时间最早的那一个，线段树维护区间内最后一次扫雪时间的最小值，然后利用二分和前缀和计算雪的厚度即可。

时间复杂度$O(q\log n)$。

#include
     
      #include
      
       using namespace std;const int N=300010,M=20000000,P=1000000007,inf=~0U>>1,inv2=(P+1)/2;int cnt,n,m,t,x,y,z,F,G,ST;char op[9];int T,tot,l[M],r[M],tag[M],val[M];struct E{  int f,g,sum,st,en;  int at(int x){return (1LL*f*(x-st+1)+g)%P;}  int cal(int l,int r){return 1LL*inv2*(at(l)+at(r))%P*(r-l+1)%P;}}e[N],now;inline void tag1(int&x,int p){  if(!x)x=++tot;  tag[x]=max(tag[x],p);  val[x]=max(val[x],p);}inline void pb(int x){  if(tag[x]){    tag1(l[x],tag[x]);    tag1(r[x],tag[x]);    tag[x]=0;  }}void change(int&x,int a,int b,int c,int d,int p){  if(!x)x=++tot;  if(c<=a&&b<=d){    tag1(x,p);    return;  }  pb(x);  int mid=(a+b)>>1;  if(c<=mid)change(l[x],a,mid,c,d,p);  if(d>mid)change(r[x],mid+1,b,c,d,p);  val[x]=min(val[l[x]],val[r[x]]);}int ask(int x,int a,int b,int c,int d){  if(c<=a&&b<=d||!x)return val[x];  pb(x);  int mid=(a+b)>>1,t=inf;  if(c<=mid)t=ask(l[x],a,mid,c,d);  if(d>mid)t=min(t,ask(r[x],mid+1,b,c,d));  return t;}inline int query(int L,int R){  if(L>R)return 0;  int l=1,r=cnt,mid,t=0;  now.f=F;  now.g=G;  now.st=ST;  now.en=R;  while(l<=r){    mid=(l+r)>>1;    if(e[mid].st>L)r=mid-1;    else if(e[mid].en
      
     

　　

E. Evaluation

求出任意一棵最小生成树。

对于每条非树边$(u,v)$，答案为这棵生成树上$u$到$v$路径上边权的最大值。

对于每条树边$(u,v)$，答案为所有非树边在树上路径中覆盖了这条边的边权的最小值。

倍增实现快速操作即可。

时间复杂度$O(m\log n)$。

#include 
     
      #define xx first#define yy second#define mp make_pair#define pb push_back#define mset(x, y) memset(x, y, sizeof x)#define mcpy(x, y) memcpy(x, y, sizeof x)using namespace std;typedef long long LL;typedef pair < int, int > pii;inline int Read(){	int x = 0, f = 1, c = getchar();	for (; !isdigit(c); c = getchar())		if (c == '-')			f = -1;	for (;  isdigit(c); c = getchar())		x = x * 10 + c - '0';	return x * f;}const int MAXN = 1000005;const int INF = 0x3f3f3f3f;int f[MAXN], u[MAXN], v[MAXN], w[MAXN], p[MAXN], n, m, g[18][MAXN], h[18][MAXN], dep[MAXN], ans[MAXN], e[18][MAXN];vector < pii > adj[MAXN], a[MAXN];bool t[MAXN];inline int Find(int x) { while (x ^ f[x]) x = f[x] = f[f[x]]; return x; }inline void Dfs(int x){	for (auto e : adj[x])	{		int y = e.xx, w = e.yy;		if (y == g[0][x])			continue;		g[0][y] = x; h[0][y] = w;		for (int i = 1; i <= 17; i ++)			g[i][y] = g[i - 1][g[i - 1][y]], h[i][y] = max(h[i - 1][y], h[i - 1][g[i - 1][y]]);		dep[y] = dep[x] + 1;		Dfs(y);	}}inline void Build(){	sort(p + 1, p + m + 1, [&](int x, int y) { return w[x] < w[y]; });	for (int i = 1; i <= n; i ++)		f[i] = i;	for (int i = 1; i <= m; i ++)	{		int x = u[p[i]], y = v[p[i]], z = w[p[i]];		if (Find(x) ^ Find(y))			f[Find(x)] = Find(y), t[p[i]] = 1, adj[x].pb(mp(y, z)), adj[y].pb(mp(x, z));	}	Dfs(1);}inline int Query(int x, int y){	int ret = 0;	if (dep[x] < dep[y])		swap(x, y);	if (dep[x] ^ dep[y])		for (int i = 17; ~i; i --)			if (dep[x] - dep[y] >> i & 1)				ret = max(ret, h[i][x]), x = g[i][x];	if (x == y)		return ret;	for (int i = 17; ~i; i --)		if (g[i][x] ^ g[i][y])			ret = max(ret, max(h[i][x], h[i][y])), x = g[i][x], y = g[i][y];	return max(ret, max(h[0][x], h[0][y]));}inline void Add(int x, int y, int w){	if (dep[x] < dep[y])		swap(x, y);	if (dep[x] ^ dep[y])		for (int i = 17; ~i; i --)			if (dep[x] - dep[y] >> i & 1)				e[i][x] = min(e[i][x], w), x = g[i][x];	if (x ^ y)	{		for (int i = 17; ~i; i --)			if (g[i][x] ^ g[i][y])				e[i][x] = min(e[i][x], w), e[i][y] = min(e[i][y], w), x = g[i][x], y = g[i][y];		e[0][x] = min(e[0][x], w);		e[0][y] = min(e[0][y], w);	}}int main(){#ifdef wxh010910	freopen("data.in", "r", stdin);#endif	n = Read(), m = Read();	for (int i = 1; i <= m; i ++)		u[i] = Read(), v[i] = Read(), w[i] = Read(), p[i] = i;	Build();	mset(e, INF);	for (int i = 1; i <= m; i ++)		if (!t[i])			ans[i] = Query(u[i], v[i]), Add(u[i], v[i], w[i]);		else if (dep[u[i]] < dep[v[i]])			f[v[i]] = i;		else			f[u[i]] = i;	for (int j = 17; j; j --)		for (int i = 1; i <= n; i ++)			e[j - 1][i] = min(e[j - 1][i], e[j][i]), e[j - 1][g[j - 1][i]] = min(e[j - 1][g[j - 1][i]], e[j][i]);	for (int i = 2; i <= n; i ++)		ans[f[i]] = e[0][i] == INF ? 1e9 : e[0][i];	for (int i = 1; i <= m; i ++)		printf("%d\n", ans[i]);	return 0;}
     

　　

F. Baking Pans

即判断$\sqrt{p}+\sqrt{d}<\sqrt{t}$是否成立，特判$p+d>t$的情况后，两边平方得$p+d+2\sqrt{pd}<t$，移项后再两边平方得$4pd<(t-p-d)^2$。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
              
             
            
           
          
         
        
       
      
     

　　

G. Taste in Art

首先将所有相同的数合并，显然每种数字要么都不选，要么都选。

将每个数看作$2^x3^yz$，对于$z$相同的那些数字，将它们以坐标$(x,y)$放在网格图上，则不能选出一个形状为$L$的$3$个点，轮廓线DP即可。

#include
     
      #include
      
       using namespace std;const int N=50010,M=19;int n,m,i,j,a[N],ans,o,f[2][1<
       
        =R){    for(i=L;i<=R;i++)ret+=e[i].z;    return ret;  }  int ymin=100;  for(i=L;i<=R;i++){    b[i]=e[i];    ymin=min(ymin,e[i].y);  }  for(i=L;i<=R;i++)b[i].y-=ymin;  o=0;  A=1;  for(j=0;j<1<
        
         L&&x==b[i-1].x){      int blank=~0U>>1;      for(j=b[i-1].y+1;j
         
          <
          
           >y&1)kk^=1<
           
            >y&1)&&(k>>(y+1)&1))continue; up(f[o^1][kk^(1<
            
             >1; for(j=oldy+1;j
             
              <
              
               >y&1)kk^=1<
               
                >y&1)&&(k>>(y+1)&1))continue; up(f[o^1][kk^(1<
               
              
             
            
           
          
         
        
       
      
     

　　

H. Hobby

方案数为$9!$，爆搜即可。

#include
     
      #include
      
       using namespace std;const int N=111;int va,vb,vc,v1,v2,v3,v4,i,q[N];char a[N][N];int s[N];bool check(){  if(q[1]+q[2]+q[4]+q[5]!=v1)return 0;  if(q[2]+q[3]+q[5]+q[6]!=v2)return 0;  if(q[4]+q[5]+q[7]+q[8]!=v3)return 0;  if(q[5]+q[6]+q[8]+q[9]!=v4)return 0;  s[0]=s[1]=s[2]=0;  s[a[1][1]-'A']+=q[1];  s[a[1][2]-'A']+=q[2];  s[a[1][3]-'A']+=q[3];  s[a[2][1]-'A']+=q[4];  s[a[2][2]-'A']+=q[5];  s[a[2][3]-'A']+=q[6];  s[a[3][1]-'A']+=q[7];  s[a[3][2]-'A']+=q[8];  s[a[3][3]-'A']+=q[9];  if(s[0]!=va)return 0;  if(s[1]!=vb)return 0;  if(s[2]!=vc)return 0;  return 1;}int main(){  scanf("%d%d%d%d%d%d%d",&va,&vb,&vc,&v1,&v2,&v3,&v4);  for(i=1;i<=3;i++)scanf("%s",a[i]+1);  for(i=1;i<=9;i++)q[i]=i;  do{    if(check()){      for(i=1;i<=9;i++){        printf("%d",q[i]);        if(i%3==0)puts("");      }      return 0;    }  }while(next_permutation(q+1,q+10));  puts("NIE");}
      
     

　　

I. Grade Book

对于两份作业$(p_i,t_i),(p_j,t_j)$，其中$t_i\leq t_j$，则交完作业$i$后能赶到$j$当且仅当$t_j-t_i\geq |p_i-p_j|$。

将绝对值拆开，有：

• $t_j-p_j\geq t_i-p_i$
• $t_j+p_j\geq t_i+p_i$

将$(t_i-p_i,t_i+p_i)$作为坐标放在平面上，那么每个点可以走到右上角的区域，根据Dilworth定理，最少所需的天数等于最长反链的大小，也就是最长下降子序列的长度。

时间复杂度$O(n\log n)$。

#include
     
      #include
      
       #include
       
        using namespace std;int n,i;set
        
         T;struct P{int x,y;}a[2222222];inline bool cmp(const P&a,const P&b){  if(a.x!=b.x)return a.x
         
          b.y;}int main(){  scanf("%d",&n);  for(i=1;i<=n;i++){    int p,t;    scanf("%d%d",&p,&t);    a[i].x=p+t;    a[i].y=p-t;  }  sort(a+1,a+n+1,cmp);  for(i=1;i<=n;i++){    int x=a[i].y;    set
          
           ::iterator it=T.lower_bound(x); if(it!=T.end())T.erase(it); T.insert(x); } printf("%d",(int)T.size());}
          
         
        
       
      
     

　　

J. Identical Scarves

将所有数排序，显然最优方案是选择一个区间并将它们调整到中位数，双指针枚举区间即可。

时间复杂度$O(n\log n)$。

#include
     
      #include
      
       using namespace std;typedef long long ll;const int N=100010;int n,i,j,a[N],ans;ll lim,s[N];inline ll cal(int l,int r){  int m=(l+r)/2;  return s[r]-s[m]-1LL*(r-m)*a[m]+1LL*(m-l+1)*a[m]-s[m]+s[l-1];}int main(){  scanf("%d%lld",&n,&lim);  for(i=1;i<=n;i++)scanf("%d",&a[i]);  sort(a+1,a+n+1);  for(i=1;i<=n;i++)s[i]=s[i-1]+a[i];  for(i=1;i<=n;i++){    while(j
       
        <=lim)j++;    ans=max(ans,j-i+1);  }  printf("%d",ans);}
       
      
     

　　

K. Pocket Money

对于最大可能值，一定是先放$+$，再放$0$，最后放$-$。

对于最小可能值，从$1$开始逐位确定，能放$-$就放$-$。

时间复杂度$O(n\log n)$。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
              
             
            
           
          
         
        
       
      
     

　　

L. Lines

因为任何一种方案都可以将$01$取反得到另一个方案，因此答案一定是$2$的倍数，所以当$P=2$时直接输出$0$。

否则$P>2$且$P$是质数，所以存在$2$的逆元。

考虑容斥，选择一些行、列和对角线，满足这些行、列、对角线上所有字符都相等，其它的不管，则对答案的贡献为$(-1)^{被打破的限制个数}2^{未被这些行、列、对角线覆盖的格子数}2^{必然相等的连通块个数}$。

对于选择了$0$条对角线的情况：

枚举选择的行数$i$和列数$j$，用组合数算出选法的数量，未被覆盖的格子数为$(n-i)(n-j)$，而连通块个数在$i\times j=0$的时候为$i+j$，否则为$1$，时间复杂度$O(n^2)$。

对于选择了$1$条对角线的情况：

连通块个数必然为$1$。

假设选择了$x$行和$y$列，那么未被覆盖的格子数为$(n-x)(n-y)$减去对角线上未被覆盖的格子数。

设$f[i][j][k]$表示考虑对角线上前$i$个格子，选了$j$行$k$列时，所有方案的容斥系数除以$2^{对角线上未被覆盖的格子数}$的和，枚举下一行下一列的选法进行转移，时间复杂度$O(n^3)$。

对于选择了$2$条对角线的情况：

和上述方法类似，设$f[i][j][k]$表示考虑$i\times i$的棋盘，选了$j$行$k$列时，所有方案的容斥系数除以$2^{对角线上未被覆盖的格子数}$的和，往外扩一圈进行转移，从$f[i][][]$转移到$f[i+2][][]$，时间复杂度$O(n^3)$。

特别要注意这种情况下，连通块个数一般都为$1$，但是当$n$是偶数且$j=k=0$时连通块个数为$2$，需要特判。

#include
     
      const int N=310;int inv2;int n,P,i,j,k,x,y,C[N][N],p[N*N],ans;int f[N][N][N],g[N][N][N],v[3][3];int pow(int a,int b){int t=1;for(;b;b>>=1,a=1LL*a*a%P)if(b&1)t=1LL*t*a%P;return t;}inline void up(int&a,int b){a=(a+b)%P;}int cal1(){  f[0][0][0]=(P-2)%P;  for(i=0;i
      
       <=i;j++)for(k=0;k<=i;k++){    up(f[i+1][j][k],1LL*f[i][j][k]*inv2%P);    up(f[i+1][j+1][k],P-f[i][j][k]);    up(f[i+1][j][k+1],P-f[i][j][k]);    up(f[i+1][j+1][k+1],f[i][j][k]);  }  int ret=0;  for(i=0;i<=n;i++)for(j=0;j<=n;j++)up(ret,1LL*f[n][i][j]*p[(n-i)*(n-j)]%P);  return ret;}int cal2(){  g[0][0][0]=2;  g[1][0][0]=1;  g[1][0][1]=g[1][1][0]=(P-2)%P;  g[1][1][1]=2;  //when n is even and i=j=0, it is different  for(x=0;x<3;x++)for(y=0;y<3;y++){    int tmp=C[2][x]*C[2][y]%P;    if((x+y)&1)tmp=(P-tmp)%P;    int cnt=(2-x)*(2-y);    while(cnt--)tmp=1LL*tmp*inv2%P;    v[x][y]=tmp;  }  for(i=0;i
       
        <=i;j++)for(k=0;k<=i;k++)    for(x=0;x<3;x++)for(y=0;y<3;y++)      up(g[i+2][j+x][k+y],1LL*v[x][y]*g[i][j][k]%P);  int ret=0;  if(n&1){    for(i=0;i<=n;i++)for(j=0;j<=n;j++)up(ret,1LL*g[n][i][j]*p[(n-i)*(n-j)]%P);  }else{    for(i=0;i<=n;i++)for(j=0;j<=n;j++)if(i||j)up(ret,1LL*g[n][i][j]*p[(n-i)*(n-j)]%P);    up(ret,p[n*n-n-n+2]);  }  return ret;}int main(){  scanf("%d%d",&n,&P);  if(P==2)return puts("0"),0;  inv2=pow(2,P-2);  for(p[0]=i=1;i<=n*n;i++)p[i]=p[i-1]*2%P;  for(C[0][0]=i=1;i<=n||i<=2;i++)for(C[i][0]=j=1;j<=i;j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%P;  //no diagonals  for(i=0;i<=n;i++)for(j=0;j<=n;j++){    int tmp=1LL*C[n][i]*C[n][j]%P*p[(n-i)*(n-j)]%P;    if(!i||!j)tmp=1LL*tmp*p[i+j]%P;else tmp=tmp*2%P;    if((i+j)&1)tmp=(P-tmp)%P;    up(ans,tmp);  }  up(ans,2LL*cal1()%P);  up(ans,cal2());  printf("%d",(ans%P+P)%P);}
       
      
     

　　

M. Magical Maze

首先剔除所有不能到达$(1,1)$和$(n,m)$的点，问题转化为对于每个点$x$，统计它能到达多少点。

注意到这是平面图，因此从$x$点出发，左手摸墙走可以走出一条到终点的路径，右手摸墙走也可以走出一条到终点的路径，把这两段路径拼起来可以得到一个简单多边形，多边形内的所有点都是$x$能到达的。

求出每条横边下方的点数，往右走时加上下面的点数，往左走时减去下面的点数，即可算出多边形内的点数。

以左手摸墙为例，设$f(i,j,k=0,1,2,3)$表示人位于$(i,j)$，左手摸着$k$方向这面墙，人位于这面墙的起点(即还没有开始摸这面墙)时，直到终点的贡献和，可以记忆化搜索求出。

对于每个点答案的计算，可以枚举两种初始朝向，取答案较大的那一个作为真正的答案。

时间复杂度$O(nm)$。

#include
     
      #include
      
       using namespace std;const int N=500010;char tmp[N];long long ans;int n,m,i,j,k,x,s[N],fl[N][4],fr[N][4],dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};bool d[N][4],v1[N],v2[N],visl[N][4],visr[N][4];/* 03 1 2*/inline int id(int x,int y){  if(x<1||x>n||y<1||y>m)return 0;  return (x-1)*m+y;}void dfs1(int x,int y){  int z=id(x,y);  if(v1[z])return;  v1[z]=1;  for(int i=0;i<4;i++)if(d[z][i])dfs1(x+dx[i],y+dy[i]);}void dfs2(int x,int y){  int z=id(x,y);  if(v2[z])return;  v2[z]=1;  for(int i=0;i<4;i++)if(d[id(x-dx[i],y-dy[i])][i])dfs2(x-dx[i],y-dy[i]);}int dpl(int x,int y,int k){//left hand on the kth wall，后退到不能再后退（即顶点）  int z=id(x,y);  if(visl[z][k])return fl[z][k];  visl[z][k]=1;  int&ret=fl[z][k];  ret=0;  if(x==n&&y==m&&(k==1||k==2))return ret;  if(d[z][k])return ret=dpl(x+dx[k],y+dy[k],(k+3)&3);  if(k==0)ret+=s[id(x,y)];  if(k==2)ret-=s[id(x+1,y)];  return ret+=dpl(x,y,(k+1)&3);}int dpr(int x,int y,int k){//right hand on the kth wall，后退到不能再后退（即顶点）  int z=id(x,y);  if(visr[z][k])return fr[z][k];  visr[z][k]=1;  int&ret=fr[z][k];  ret=0;  if(x==n&&y==m&&(k==1||k==2))return ret;  if(d[z][k])return ret=dpr(x+dx[k],y+dy[k],(k+1)&3);  if(k==0)ret+=s[id(x,y)];  if(k==2)ret-=s[id(x+1,y)];  return ret+=dpr(x,y,(k+3)&3);}int main(){  scanf("%d%d",&n,&m);  for(i=1;i<=n;i++){    if(m>1)scanf("%s",tmp+1);    for(j=1;j
       
        ')d[id(i,j)][1]=1;      if(tmp[j]=='<')d[id(i,j+1)][3]=1;    }    if(i==n)continue;    scanf("%s",tmp+1);    for(j=1;j<=m;j++){      if(tmp[j]=='v')d[id(i,j)][2]=1;      if(tmp[j]=='^')d[id(i+1,j)][0]=1;    }  }  dfs1(1,1);  dfs2(n,m);  for(i=1;i<=n;i++)for(j=1;j<=m;j++)v1[id(i,j)]&=v2[id(i,j)];  for(i=1;i<=n;i++)for(j=1;j<=m;j++){    x=id(i,j);    if(!v1[x])for(k=0;k<4;k++)d[x][k]=0;    for(k=0;k<4;k++)if(!v1[id(i+dx[k],j+dy[k])])d[x][k]=0;  }  for(i=n;i;i--)for(j=1;j<=m;j++)s[id(i,j)]=s[id(i+1,j)]+v1[id(i,j)];  for(i=1;i<=n;i++)for(j=1;j<=m;j++){    x=id(i,j);    if(!v1[x])continue;    ans+=max(dpl(i,j,0)+dpr(i,j,3),dpl(i,j,2)+dpr(i,j,1));  }  printf("%lld",ans);}