oj.uz

Submission #717982

# Submission time Handle Problem Language Result Execution time Memory
717982 2023-04-03T05:15:10 Z vinnipuh01 Soccer (JOI17_soccer) C++17
0 / 100
 600 ms 254236 KB 
#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <stack>
#include <string>
#include <map>
#include <queue>
#define int long long
#define sqrt sqrtl

using namespace std;

const long long oo = 1000000000000000000;

long long sum, ans = 0, mx = 0, mn = 1000000000, num, pos;


/*
    ViHHiPuh

   (( `'-""``""-'` ))
     )-__-_.._-__-(
   / --- (o _ o) --- \
   \ .-* ( .0. ) *-. /
   _'-. ,_ '=' _, .-'_
  / `;#'#'# - #'#'#;` \
 \_)) -----'#'----- ((_/
      # --------- #
  '# ------- ------ #'
  /..-'# ------- #'-.\
  _\...-\'# -- #'/-.../_
  ((____)- '#' -(____))


    cout << fixed << setprecision(6) << x;

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    freopen ( "sum.in", "r", stdin )
*/

int h, w, n, x[ 100001 ], y[ 100001 ], a, b, c;

vector <pair<pair<int, int>, int> > v[ 3 ][ 250001 ];
int d[ 501 ][ 501 ];
int dp[ 3 ][ 250001 ];
set <pair< int, pair<int, int> > > st;

main () {
	cin >> h >> w;
	cin >> a >> b >> c;
	cin >> n;
	for ( int i = 0; i <= h; i ++ ) {
		for ( int j = 0; j <= w; j ++ )
			d[ i ][ j ] = oo;
	}
	for ( int i = 1; i <= n; i ++ ) {
		cin >> x[ i ] >> y[ i ];
		for ( int j = 0; j <= h; j ++ ) {
			d[ j ][ y[ i ] ] = min( d[ j ][ y[ i ] ], abs( x[ i ] - j ) );
		}
		for ( int j = 0; j <= w; j ++ )
			d[ x[ i ] ][ j ] = min( d[ x[ i ] ][ j ], abs( j - y[ i ] ) );
	}
	for ( int i = 0; i <= h; i ++ ) {
		for ( int j = 0; j <= w; j ++ ) {
			for ( int k = 0; k <= h; k ++ )
				d[ i ][ j ] = min( d[ i ][ j ], d[ k ][ j ] + abs( k - i ) );
			for ( int k = 1; k <= w; k ++ )
				d[ i ][ j ] = min( d[ i ][ j ], d[ i ][ k ] + abs( k - j ) );
		}
	}
	for ( int i = 0; i <= h; i ++ ) {
		for ( int j = 0; j <= w; j ++ ) {
			num = ( i ) * ( w + 1 ) + j;
			v[ 0 ][ num ].push_back( { make_pair( 1, num ), b } );
			v[ 0 ][ num ].push_back( { make_pair( 2, num ), b } );
			v[ 1 ][ num ].push_back( { make_pair( 0, num ), d[ i ][ j ] * c } );
			v[ 2 ][ num ].push_back( { make_pair( 0, num ), d[ i ][ j ] * c } );
			if ( i ) {
				v[ 0 ][ num ].push_back( { make_pair( 0, num - w - 1 ), c } );
				v[ 1 ][ num ].push_back( { make_pair( 1, num - w - 1 ), a } );
			}
			if ( i < h ) {
				v[ 0 ][ num ].push_back( { make_pair( 0, num + w + 1 ), c } );
				v[ 1 ][ num ].push_back( { make_pair( 1, num + w + 1 ), a } );
			}
			if ( j ) {
				v[ 0 ][ num ].push_back( { make_pair( 0, num - 1 ), c } );
				v[ 2 ][ num ].push_back( { make_pair( 2, num - 1 ), a } );
			}
			if ( j < w ) {
				v[ 0 ][ num ].push_back( { make_pair( 0, num + 1 ), c } );
				v[ 2 ][ num ].push_back( { make_pair( 2, num + 1 ), a } );
			}
		}
	}
	for ( int i = 0; i <= ( h + 1 ) * ( w + 1 ); i ++ )
		for ( int j = 0; j < 3; j ++ )
			dp[ j ][ i ] = oo;
	dp[ 0 ][ x[ 1 ] * ( w + 1 ) + y[ 1 ] ] = 0;
	st.insert( { 0, make_pair( 0, x[ 1 ] * ( w + 1 ) + y[ 1 ] ) } );
	while ( st.size() ) {
		pair<int, int> p = st.begin()->second;
		st.erase( st.begin() );
		for ( auto to : v[ p.first ][ p.second ] ) {
			if ( dp[ to.first.first ][ to.first.second ] > dp[ p.first ][ p.second ] + to.second ) {
				st.erase( { dp[ to.first.first ][ to.first.second ], to.first } );
				dp[ to.first.first ][ to.first.second ] = dp[ p.first ][ p.second ] + to.second;
				st.insert( { dp[ to.first.first ][ to.first.second ], to.first } );
			}
		}
	}
	cout << dp[ 0 ][ x[ n ] * ( w + 1 ) + y[ n ]  ];
}

/*



1 - kick x
2 - kick y
0 - go

*/

Compilation message

soccer.cpp:54:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   54 | main () {
      | ^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 48268 KB Output is correct
2 Correct 11 ms 18016 KB Output is correct
3 Runtime error 568 ms 254156 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 600 ms 254236 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 48268 KB Output is correct
2 Correct 11 ms 18016 KB Output is correct
3 Runtime error 568 ms 254156 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -