#957190 (C++17) No.957 植林

提出ソース
結果

問題	No.957 植林
コンテスト
ユーザー	gosou513
提出日時	2024-03-02 16:54:56
言語	C++17 (gcc 13.3.0 + boost 1.87.0)
結果	TLE
実行時間	-
コード長	13,933 bytes
コンパイル時間	2,448 ms
コンパイル使用メモリ	209,020 KB
最終ジャッジ日時	2025-02-19 23:50:52
ジャッジサーバーID （参考情報）	judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 3
other	AC * 15 TLE * 1 -- * 29
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair< int, int >;
using pll = pair< ll, ll >;
template< class T > using vc = vector< T >;
template< class T > using vvc = vector< vector< T > >;
template< class T > using vvvc = vector< vector< vector< T > > >;
template< class T > using vvvvc = vector< vector< vector< vector< T > > > >;
template< class T > using pq = priority_queue< T >;
template< class T > using pqg = priority_queue< T, vector< T >, greater< T > >;
template< class T > using mset = multiset< T >;
template< class T > using uset = unordered_set< T >;
template< class T, class U > using umap = unordered_map< T, U >;
template< class T > struct Edge {
    int from, to;
    T cost;
    int id;
    Edge( int from_, int to_, T cost_ = 1, int id_ = -1 ) : from( from_ ), to( to_ ), cost( cost_ ), id( id_ ) {}
};
template< class T > struct Graph {
    vector< vector< Edge< T > > > G;
    int e;
    bool is_directed;

    Graph() {}
    Graph( int n, bool is_directed_ = false ) : G( n ), e( 0 ), is_directed( is_directed_ ) {}
    int size() const {
        return G.size();
    }
    void add_edge( int from, int to, T cost = 1 ) {
        G[ from ].emplace_back( from, to, cost, e );
        if ( !is_directed ) G[ to ].emplace_back( to, from, cost, e );
        e++;
    }
    void add_edge( int from, int to, T cost, int id ) {
        G[ from ].emplace_back( from, to, cost, id );
        if ( !is_directed ) G[ to ].emplace_back( to, from, cost, id );
        e++;
    }
    inline vector< Edge< T > > &operator[]( int i ) {
        return G[ i ];
    }
};
template< class T > using Edges = vector< Edge< T > >;

#define vec( type, name, ... ) vector< type > name( __VA_ARGS__ )
#define vv( type, name, h, ... ) vector name( h, vector< type >( __VA_ARGS__ ) )
#define vvv( type, name, h, w, ... ) vector name( h, vector( w, vector< type >( __VA_ARGS__ ) ) )
#define vvvv( type, name, a, b, c, ... ) vector< vector< vector< vector< type > > > > name( a, vector< vector< vector< type > > >( b, vector< vector< type > >( c, vector< type >( __VA_ARGS__ ) ) ) )

const int INF = 0x3fffffff;
const ll LINF = 0x1fffffffffffffff;
const ld DINF = numeric_limits< ld >::infinity();
const ld EPS = 1e-10;
const ld PI = 3.1415926535897932;
const ll dx[] = { 0, 1, 0, -1, 1, -1, 1, -1 };
const ll dy[] = { 1, 0, -1, 0, 1, 1, -1, -1 };

#define overload5( a, b, c, d, e, name, ... ) name
#define overload4( a, b, c, d, name, ... ) name
#define overload3( a, b, c, name, ... ) name
#define rep0( n ) for ( ll qwerty = 0; qwerty < n; qwerty++ )
#define rep1( i, n ) for ( ll i = 0; i < ( n ); i++ )
#define rep2( i, a, b ) for ( ll i = ( a ); i < ( b ); i++ )
#define rep3( i, a, b, c ) for ( ll i = ( a ); i < ( b ); i += ( c ) )
#define rep( ... ) overload4( __VA_ARGS__, rep3, rep2, rep1, rep0 )( __VA_ARGS__ )
#define rrep0( n ) for ( ll qwerty = (n)-1; qwerty >= 0; qwerty-- )
#define rrep1( i, n ) for ( ll i = (n)-1; i >= 0; i-- )
#define rrep2( i, a, b ) for ( ll i = (a)-1; i >= ( b ); i-- )
#define rrep3( i, a, b, c ) for ( ll i = (a)-1; i >= ( b ); i -= ( c ) )
#define rrep( ... ) overload4( __VA_ARGS__, rrep3, rrep2, rrep1, rrep0 )( __VA_ARGS__ )
#define each1( i, a ) for ( auto &&i : a )
#define each2( x, y, a ) for ( auto &&[ x, y ] : a )
#define each3( x, y, z, a ) for ( auto &&[ x, y, z ] : a )
#define each4( w, x, y, z, a ) for ( auto &&[ w, x, y, z ] : a )
#define each( ... ) overload5( __VA_ARGS__, each4, each3, each2, each1 )( __VA_ARGS__ )
#define all1( i ) begin( i ), end( i )
#define all2( i, a ) begin( i ), begin( i ) + a
#define all3( i, a, b ) begin( i ) + a, begin( i ) + b
#define all( ... ) overload3( __VA_ARGS__, all3, all2, all1 )( __VA_ARGS__ )
#define rall1( i ) rbegin( i ), rend( i )
#define rall2( i, a ) rbegin( i ), rbegin( i ) + a
#define rall3( i, a, b ) rbegin( i ) + a, rbegin( i ) + b
#define rall( ... ) overload3( __VA_ARGS__, rall3, rall2, rall1 )( __VA_ARGS__ )

#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define Endl '\n'
#define ifnot( x ) if ( !( x ) )
#define YesNo( x ) cout << ( x ? "Yes" : "No" ) << endl;

#define bit( i ) ( 1LL << ( i ) )
#define getbit( x, i ) ( ( ( x ) >> ( i ) ) & 1 )
#define topbit( x ) ( ( x ) == 0 ? -1 : 63 - __builtin_clzll( x ) )
#define lowbit( x ) ( ( x ) == 0 ? 64 : __builtin_ctzll( x ) )
#define popcount( x ) __builtin_popcountll( x )
#define mask( i ) ( ( 1LL << ( i ) ) - 1 )

template< class T > vector< T > &operator++( vector< T > &v ) {
    for ( auto &e : v ) e++;
    return v;
}
template< class T > vector< T > operator++( vector< T > &v, signed ) {
    auto res = v;
    for ( auto &e : v ) e++;
    return res;
}
template< class T > vector< T > &operator--( vector< T > &v ) {
    for ( auto &e : v ) e--;
    return v;
}
template< class T > vector< T > operator--( vector< T > &v, signed ) {
    auto res = v;
    for ( auto &e : v ) e--;
    return res;
}
template< class T, class U > istream &operator>>( istream &is, pair< T, U > &p ) {
    is >> p.first >> p.second;
    return is;
}
template< class T, class U > ostream &operator<<( ostream &os, const pair< T, U > &p ) {
    os << p.first << ' ' << p.second;
    return os;
}
template< class T > istream &operator>>( istream &is, vector< T > &v ) {
    for ( auto &e : v ) is >> e;
    return is;
}
template< class T > ostream &operator<<( ostream &os, const vector< T > &v ) {
    for ( auto &e : v ) os << e << ' ';
    return os;
}
template< class T > ostream &operator<<( ostream &os, const vector< vector< T > > &v ) {
    for ( auto &e : v ) {
        for ( auto &c : e ) os << c << ' ';
        os << endl;
    }
    return os;
}

#define INT( ... )   \
    int __VA_ARGS__; \
    IN( __VA_ARGS__ )
#define INTd( ... )  \
    int __VA_ARGS__; \
    IN2( __VA_ARGS__ )
#define LL( ... )   \
    ll __VA_ARGS__; \
    IN( __VA_ARGS__ )
#define LLd( ... )  \
    ll __VA_ARGS__; \
    IN2( __VA_ARGS__ )
#define STR( ... )      \
    string __VA_ARGS__; \
    IN( __VA_ARGS__ )
#define CHR( ... )    \
    char __VA_ARGS__; \
    IN( __VA_ARGS__ )
#define DBL( ... )      \
    double __VA_ARGS__; \
    IN( __VA_ARGS__ )
#define LD( ... )            \
    long double __VA_ARGS__; \
    IN( __VA_ARGS__ )
#define VEC( type, name, size )  \
    vector< type > name( size ); \
    IN( name )
#define VECd( type, name, size ) \
    vector< type > name( size ); \
    IN2( name )
#define VEC2( type, name1, name2, size )         \
    vector< type > name1( size ), name2( size ); \
    for ( int i = 0; i < size; i++ ) IN( name1[ i ], name2[ i ] )
#define VEC2d( type, name1, name2, size )        \
    vector< type > name1( size ), name2( size ); \
    for ( int i = 0; i < size; i++ ) IN2( name1[ i ], name2[ i ] )
#define VEC3( type, name1, name2, name3, size )                 \
    vector< type > name1( size ), name2( size ), name3( size ); \
    for ( int i = 0; i < size; i++ ) IN( name1[ i ], name2[ i ], name3[ i ] )
#define VEC3d( type, name1, name2, name3, size )                \
    vector< type > name1( size ), name2( size ), name3( size ); \
    for ( int i = 0; i < size; i++ ) IN2( name1[ i ], name2[ i ], name3[ i ] )
#define VEC4( type, name1, name2, name3, name4, size )                         \
    vector< type > name1( size ), name2( size ), name3( size ), name4( size ); \
    for ( int i = 0; i < size; i++ ) IN( name1[ i ], name2[ i ], name3[ i ], name4[ i ] );
#define VEC4d( type, name1, name2, name3, name4, size )                        \
    vector< type > name1( size ), name2( size ), name3( size ), name4( size ); \
    for ( int i = 0; i < size; i++ ) IN2( name1[ i ], name2[ i ], name3[ i ], name4[ i ] );
#define VV( type, name, h, w )                               \
    vector< vector< type > > name( h, vector< type >( w ) ); \
    IN( name )
#define VVd( type, name, h, w )                              \
    vector< vector< type > > name( h, vector< type >( w ) ); \
    IN2( name )
int scan() {
    return getchar();
}
void scan( int &a ) {
    cin >> a;
}
void scan( long long &a ) {
    cin >> a;
}
void scan( char &a ) {
    cin >> a;
}
void scan( double &a ) {
    cin >> a;
}
void scan( string &a ) {
    cin >> a;
}
template< class T, class S > void scan( pair< T, S > &p ) {
    scan( p.first ), scan( p.second );
}
template< class T > void scan( vector< T > & );
template< class T > void scan( vector< T > &a ) {
    for ( auto &i : a ) scan( i );
}
template< class T > void scan( T &a ) {
    cin >> a;
}
void IN() {}
void IN2() {}
template< class Head, class... Tail > void IN( Head &head, Tail &...tail ) {
    scan( head );
    IN( tail... );
}
template< class Head, class... Tail > void IN2( Head &head, Tail &...tail ) {
    scan( head );
    --head;
    IN2( tail... );
}

template< class T, class S > bool inc( const T &x, const S &l, const S &r ) {
    return l <= x && x < r;
}
template< typename T > int si( const T &x ) {
    return x.size();
}
template< class T, class S > inline bool chmax( T &a, const S &b ) {
    return ( a < b ? a = b, 1 : 0 );
}
template< class T, class S > inline bool chmin( T &a, const S &b ) {
    return ( a > b ? a = b, 1 : 0 );
}
vector< int > iota( int n, int s = 0 ) {
    vector< int > ret( n );
    iota( ret.begin(), ret.end(), s );
    return ret;
}
template< class T > void sort( T &v ) {
    sort( v.begin(), v.end() );
}
template< class T > void rsort( T &v ) {
    sort( v.rbegin(), v.rend() );
}
template< class T > void reverse( T &v ) {
    reverse( v.begin(), v.end() );
}
template< class T > auto max( const T &a ) {
    return *max_element( a.begin(), a.end() );
}
template< class T > auto min( const T &a ) {
    return *min_element( a.begin(), a.end() );
}
template< class T > int max_id( const T &a ) {
    return max_element( a.begin(), a.end() ) - a.begin();
}
template< class T > int min_id( const T &a ) {
    return min_element( a.begin(), a.end() ) - a.begin();
}
template< class T, class S > int lb( vector< T > &v, S a ) {
    return lower_bound( v.begin(), v.end(), (T)a ) - v.begin();
}
template< class T, class S > int ub( vector< T > &v, S a ) {
    return upper_bound( v.begin(), v.end(), (T)a ) - v.begin();
}
template< typename T = ll, typename S > T sum( const S &v ) {
    return accumulate( v.begin(), v.end(), T( 0 ) );
}
template< class T > vector< T > uniq( vector< T > v ) {
    sort( v.begin(), v.end() );
    v.erase( unique( v.begin(), v.end() ), v.end() );
    return v;
}

long long max( int x, long long y ) {
    return max( (long long)x, y );
}
long long max( long long x, int y ) {
    return max( x, (long long)y );
}
long long min( int x, long long y ) {
    return min( (long long)x, y );
}
long long min( long long x, int y ) {
    return min( x, (long long)y );
}
template< class T, class S > T floor( T x, S y ) {
    if ( y < 0 ) x = -x, y = -y;
    return ( x >= 0 ? x / y : ( x - y + 1 ) / y );
}
template< class T, class S > T ceil( T x, S y ) {
    if ( y < 0 ) x = -x, y = -y;
    return ( x >= 0 ? ( x + y - 1 ) / y : x / y );
}

template< class T > class Dinic {
    struct FlowEdge {
        int to;
        T cap;
        int rev;
        bool is_rev;
        int idx;
        FlowEdge( int to_, T cap_, int rev_, bool is_rev_, int idx_ ) : to( to_ ), cap( cap_ ), rev( rev_ ), is_rev( is_rev_ ), idx( idx_ ) {}
    };
    bool bfs( int s, int t ) {
        min_cost.assign( N, -1 );
        min_cost[ s ] = 0;
        queue< int > q;
        q.push( s );
        while ( !q.empty() ) {
            int v = q.front();
            q.pop();
            for ( auto &e : G[ v ] ) {
                if ( e.cap > 0 && min_cost[ e.to ] == -1 ) {
                    min_cost[ e.to ] = min_cost[ v ] + 1;
                    q.push( e.to );
                }
            }
        }
        return min_cost[ t ] != -1;
    }
    T dfs( int v, int t, T flow ) {
        if ( v == t ) return flow;
        for ( int &i = pos[ v ]; i < (int)G[ v ].size(); i++ ) {
            FlowEdge &e = G[ v ][ i ];
            if ( e.cap > 0 && min_cost[ e.to ] > min_cost[ v ] ) {
                T f = dfs( e.to, t, min( flow, e.cap ) );
                if ( f > 0 ) {
                    e.cap -= f;
                    G[ e.to ][ e.rev ].cap += f;
                    return f;
                }
            }
        }
        return 0;
    }

   public:
    vector< vector< FlowEdge > > G;
    vector< int > min_cost, pos;
    const T INF_T;
    const int N;

    Dinic( int N_, T INF_T_ = numeric_limits< T >::max() / 2 ) : G( N_ ), min_cost( N_ ), pos( N_ ), INF_T( INF_T_ ), N( N_ ) {}
    void add_edge( int from, int to, T cap, int idx = -1 ) {
        G[ from ].emplace_back( to, cap, (int)G[ to ].size(), false, idx );
        G[ to ].emplace_back( from, 0, (int)G[ from ].size() - 1, true, idx );
    }
    // min_costが最小カットの1つ(0以上ならs側、-1ならt側)
    T max_flow( int s, int t ) {
        T flow = 0;
        while ( bfs( s, t ) ) {
            pos.assign( N, 0 );
            T f;
            while ( ( f = dfs( s, t, INF_T ) ) > 0 ) flow += f;
        }
        return flow;
    }
};

int main() {
    cin.tie( 0 );
    ios::sync_with_stdio( false );
    cout << fixed << setprecision( 15 );

    INT( H, W );
    Dinic< ll > dinic( H * W + H + W + 2, LINF );
    rep( i, H ) rep( j, W ) {
        LL( G );
        dinic.add_edge( i * W + j, H * W + H + W + 1, G );
    }
    ll sm = 0;
    rep( i, H ) {
        LL( R );
        dinic.add_edge( H * W + H + W, H * W + i, R );
        sm += R;
    }
    rep( j, W ) {
        LL( C );
        dinic.add_edge( H * W + H + W, H * W + H + j, C );
        sm += C;
    }

    rep( i, H ) rep( j, W ) {
        dinic.add_edge( H * W + i, i * W + j, LINF );
        dinic.add_edge( H * W + H + j, i * W + j, LINF );
    }

    cout << sm - dinic.max_flow( H * W + H + W, H * W + H + W + 1 ) << endl;
}
yukicoder

結果

ソースコード
