yukicoder No.866 - レベルKの正方形

Source

ニコニコミュニティ
問題文

問題概要

省略

解法

省略

cLay（version 20190820-1）のコード

C++に変換後のコードはこちら

int X, Y, K;
char C[2000][2002];

int g[2001][2001][26];

inline int getSum(int k, int i, int j, int v){
  if(g[i+v][j+v][k] - g[i][j+v][k] - g[i+v][j][k] + g[i][j][k]) return 1;
  return 0;
}

inline int getSum(int i, int j, int v){
  int k, res = 0;
  rep(k,26) res += getSum(k,i,j,v);
  return res;
}

{
  int i, j, k;
  int ii, jj, v1, v2;
  ll res = 0;
  
  rd(X,Y,K,C(X));

  rep(i,X) rep(j,Y) C[i][j] -= 'a';

  rep(i,X) rep(j,Y){
    rep(k,26) g[i+1][j+1][k] = g[i+1][j][k] + g[i][j+1][k] - g[i][j][k];
    g[i+1][j+1][C[i][j]]++;
  }

  rep(ii,X) rep(jj,Y) if(ii==0 || jj==0){
    i = ii; j = jj; v1 = v2 = 0;
    for(;;){
      while( i+v2+1 <= X && j+v2+1 <= Y && getSum(i,j,v2+1) <= K-1 ) v2++;
      v1 >?= v2;
      while( i+v1+1 <= X && j+v1+1 <= Y && getSum(i,j,v1+1) <= K   ) v1++;
      res += v1 - v2;
      i++; j++; v1--; v2--;
      if(i==X || j==Y) break;
    }
  }

  wt(res);
}

Current time: 2024年04月25日13時27分57秒
Last modified: 2019年08月21日06時07分56秒 (by laycrs)
Tags: Competitive_Programming_Incomplete yukicoder
トップページに戻る

Logged in as: unknown user (not login)