Submission #444823

#	Time	Username	Problem	Language	Result	Execution time	Memory
444823		raid	T-Covering (eJOI19_covering)	C++17	100 / 100	366 ms	22164 KiB

covering

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

int n, m, k;

bool out( int i, int j ) { 
  return i < 1 || i > n || j < 1 || j > m;
}

int dx[12] = { -1, 0, 1, 0, 1, -1, -1, 1, -2, 0, 2, 0 };
int dy[12] = { 0, -1, 0, 1, 1, 1, -1, -1, 0, -2, 0, 2 };

int dxv[4] = { -1, 0, 1, 0 };
int dyv[4] = { 0, 1, 0, -1 };

vector<pair<int, int>> cell;
vector<int> winn;
vector<vector<int>> viz;
vector<vector<int>> w, t;

void dfs( int x, int y ) {
  cell.push_back({ x, y });
  viz[x][y] = 1;
  for ( int dir = 0; dir < 12; ++dir ) {
	int nx = x + dx[dir], ny = y + dy[dir];
    if ( !out( nx, ny ) && !viz[nx][ny] && t[nx][ny] ) {
      dfs( x + dx[dir], y + dy[dir] );
	}
  }
}

int maxWin() { 
  int ngh = 0;
  int s = 0;
  for ( int i = 0; i < cell.size(); ++i ) {
	viz[cell[i].first][cell[i].second] = 2;
	++ngh;
	s += w[cell[i].first][cell[i].second];
	for ( int d = 0; d < 4; ++d ) {
	  int nx = cell[i].first + dxv[d];
	  int ny = cell[i].second + dyv[d];
	  if ( !out( nx, ny ) && !t[nx][ny] && viz[nx][ny] != 2 ) {
        ++ngh;
        s += w[nx][ny];
		winn.push_back( w[nx][ny] );
		viz[nx][ny] = 2;
	  }
	}
  }
  sort( winn.begin(), winn.end() );
  reverse( winn.begin(), winn.end() );
  if ( 4 * cell.size() > ngh ) {
    return -1;
  }
  int diff = ngh - 4 * cell.size();
  while ( diff-- ) {
	s -= winn.back();
	winn.pop_back();
  }
  winn.clear();
  return s;
}

int main() {
  cin >> n >> m;
  
  int x;
  vector<int> a, b, c;
  for ( int i = 1; i <= m; ++i ) {
    a.push_back( 0 );
    b.push_back( 0 );
	c.push_back( 1 );
  }
  w.push_back( a );
  t.push_back( b );
  viz.push_back( c );  
  for ( int i = 1; i <= n; ++i ) {
	a.clear();
	b.clear();
	c.clear();
	a.push_back( 0 );
	b.push_back( 0 );
	c.push_back( 1 );
	for ( int j = 1; j <= m; ++j ) {
	  cin >> x;  
      a.push_back( x );
	  b.push_back( 0 );	  
	  c.push_back( 0 );
	}
	w.push_back( a );
    t.push_back( b );
	viz.push_back( c );
  }
  cin >> k;
  for ( int i = 0; i < k; ++i ) {
    int x, y;
	cin >> x >> y;
	t[x + 1][y + 1] = 1;
  }
  int res = 0;
  bool ok = true;
  for ( int i = 1; i <= n; ++i ) {
	for ( int j = 1; j <= m; ++j ) {
	  if ( !viz[i][j] && t[i][j] == 1 ) {
	    dfs( i, j );
	    x = maxWin();
		if ( x == -1 ) {
		  ok = false;
		}
		res += x;
	    cell.clear();
	  }
	}
  }
  if ( ok ) {
	cout << res;
  } else {
    cout << "No";
  }
  return 0;
}

Compilation message (stderr)

covering.cpp: In function 'int maxWin()':
covering.cpp:39:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   for ( int i = 0; i < cell.size(); ++i ) {
      |                    ~~^~~~~~~~~~~~~
covering.cpp:56:24: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   56 |   if ( 4 * cell.size() > ngh ) {
      |        ~~~~~~~~~~~~~~~~^~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 15 / 15
• Subtask 6: 20 / 20
• Subtask 7: 30 / 30