SRM349Div2

250

class DocumentSearch {
public:
  int nonIntersecting(vector <string> doc, string search) {
    string s;
    for(int i=0; i<doc.size(); ++i){
      s += doc[i];
    }
    int cnt = 0;
    for(int i=0; i+search.size()<=s.size(); ++i){
      bool flg = s.substr( i, search.size() ) == search;
      cnt += flg;
      if( flg )i += (int)search.size() - 1;
    }
    return cnt;
  }
};

500

double dist_pp(double x1, double y1, double x2, double y2)
{
  double x = x1 - x2;
  double y = y1 - y2;
  return sqrt( x * x + y * y );
}

class RadarFinder {
public:
  int possibleLocations(int x1, int y1, int r1, int x2, int y2, int r2) {

    if( x1 == x2 && y1 == y2 && r1 == r2 )return -1;

    double dist_cc = dist_pp( x1, y1, x2, y2 );
    if( (double)(r1 + r2) < dist_cc )return 0;
    if( fabs(r1 - r2) > dist_cc )return    0;
    if( (double)(r1 + r2) == dist_cc )return 1;
    if( fabs(r1 - r2) == dist_cc )return 1;
    return 2;
  }
};

1000

lli dp(vector<string> g, string s)
{
  const int H = g.size();
  const int W = g[0].size();
  const int L = s.size();
  
  lli t[H][W][L];
  fill( &t[0][0][0], &t[H-1][W-1][L], 0 );

  for(int i=0; i<H; ++i){
    for(int j=0; j<W; ++j){
      if( g[i][j] == s[0] ) t[i][j][0] = 1;
    }
  }

  for(int l=0; l+1<L; ++l){
    for(int i=0; i<H; ++i){
      for(int j=0; j<W; ++j){
        if( t[i][j][l] == 0LL )continue;
        const int di[] = {-1, -1, -1, 0, 0, 1, 1, 1};
        const int dj[] = {-1, 0, 1, -1, 1, -1, 0, 1};
        for(int d=0; d<8; ++d){
          int ni = i + di[d];
          int nj = j + dj[d];
          if( ni < 0 || nj < 0 )continue;
          if( H <= ni || W <= nj )continue;
          if( g[ni][nj] == s[l+1] ){
            t[ni][nj][l+1] += t[i][j][l];
            t[ni][nj][l+1] %= mod;
          }
        }
      }
    }
  }
  
  lli sum = 0;
  for(int i=0; i<H; ++i){
    for(int j=0; j<W; ++j){
      sum += t[i][j][L-1];
      sum %= mod;
    }
  }
  sum *= (lli)s.size() * (lli)s.size();
  return sum % mod;
}

class BoggleScore {
public:
  long long bestScore(vector <string> grid, vector <string> words) {

    lli ret = 0;    
    for(int i=0;i <words.size(); ++i){
      ret = (ret + dp(grid, words[i])) % mod;
    }
    return ret;
  }
};