Untitled

 avatar
unknown
c_cpp
2 years ago
3.3 kB
4
Indexable
#pragma GCC optimize( 3 )
#include <time.h>

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
const double EPS = 1e-9;
const int INF = 0x3fffffff;
const long long LLINF = 9223372036854775807;
const double PI = acos( -1.0 );

inline int
READ()
{
   char ch;
   while( ( ch = getchar() ) < 48 || 57 < ch )
      ;
   int ans = ch - 48;
   while( 48 <= ( ch = getchar() ) && ch <= 57 )
      ans = ( ans << 3 ) + ( ans << 1 ) + ch - 48;
   return ans;
}

#define rep( i, a, b ) for( int i = ( a ); i <= ( b ); i++ )
#define per( i, a, b ) for( int i = ( a ); i >= ( b ); i-- )
#define FOREACH( i, t ) \
   for( typeof( t.begin() ) i = t.begin(); i != t.end(); i++ )
#define MP( x, y ) make_pair( x, y )
#define PB( x ) push_back( x )
#define SET( a ) memset( a, -1, sizeof( a ) )
#define CLR( a ) memset( a, 0, sizeof( a ) )
#define MEM( a, x ) memset( a, x, sizeof( a ) )
#define ALL( x ) begin( x ), end( x )
#define LL long long
#define Lson ( index * 2 )
#define Rson ( index * 2 + 1 )
#define pii pair<int, int>
#define pll pair<LL, LL>
#define MOD ( (int)1000000007 )
#define MAXN 100 + 5
///**********************************START*********************************///

int dr[] = { 1, -1, 0, 0, 0 };
int dc[] = { 0, 0, 1, -1, 0 };

int a[MAXN][MAXN][MAXN];
int f[MAXN][MAXN][MAXN];
bool v[MAXN][MAXN][MAXN];

int n, p, b;
int sr, sc;
int mxt = -1;

bool
legal( int x, int y )
{
   return x >= 1 && x <= n && y >= 1 && y <= n;
}

int
dp( int x, int y, int t )
{
   if( v[x][y][t] != 0 ) return f[x][y][t];
   v[x][y][t] = 1;

   int mx = -INF;

   rep( i, 0, 4 )
   {
      int nx = x + dr[i];
      int ny = y + dc[i];
      int nt = t - 1;
      if( legal( nx, ny ) && nt >= 0 )
      {
         mx = max( mx, dp( nx, ny, nt ) );
      }
   }

   if( a[x][y][t] > 0 )
      f[x][y][t] = mx + a[x][y][t];
   else if( a[x][y][t] == -1 )
      f[x][y][t] = mx - ceil( 1.0 * mx / 2 );
   else
      f[x][y][t] = mx;

   return f[x][y][t];
}

int
main()
{
#ifndef ONLINE_JUDGE
   freopen( "input.txt", "r", stdin );
#endif
   memset( v, 0, sizeof( v ) );
   memset( a, 0, sizeof( a ) );
   memset( f, 0, sizeof( f ) );

   scanf( "%d %d %d", &n, &p, &b );
   scanf( "%d %d", &sr, &sc );
   sr++, sc++;
   int x, y, t;
   rep( i, 1, p )
   {
      scanf( "%d %d %d", &x, &y, &t );
      x++, y++;
      a[x][y][t] += 1;
      mxt = max( mxt, t );
   }
   rep( i, 1, b )
   {
      scanf( "%d %d %d", &x, &y, &t );
      x++, y++;
      a[x][y][t] = -1;
      mxt = max( mxt, t );
   }

   rep( i, 1, n ) rep( j, 1, n )
   {
      v[i][j][0] = 1;
      if( i == sr && j == sc )
         f[i][j][0] = 0;
      else
         f[i][j][0] = -INF;
   }

   int ans = 0;
   rep( i, 1, n ) rep( j, 1, n ) ans = max( ans, dp( i, j, mxt ) );

   // rep( i, 1, n ) rep( j, 1, n ) rep( t, 1, mxt ) cout
   //     << i << " " << j << " " << t << " " << f[i][j][t] << endl;

   cout << ans << endl;

   return 0;
}
Editor is loading...