oj.uz

Submission #717983

# Submission time Handle Problem Language Result Execution time Memory
717983 2023-04-03T05:18:55 Z vinnipuh01 Soccer (JOI17_soccer) C++17
100 / 100
 1167 ms 147408 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 ][ 501 * 501 + 1 ];
int d[ 502 ][ 502 ];
int dp[ 3 ][ 501 * 501 ];
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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 48236 KB Output is correct
2 Correct 9 ms 18004 KB Output is correct
3 Correct 810 ms 141244 KB Output is correct
4 Correct 886 ms 142324 KB Output is correct
5 Correct 200 ms 60572 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 914 ms 145096 KB Output is correct
2 Correct 883 ms 145908 KB Output is correct
3 Correct 601 ms 118896 KB Output is correct
4 Correct 667 ms 140164 KB Output is correct
5 Correct 630 ms 119244 KB Output is correct
6 Correct 674 ms 143996 KB Output is correct
7 Correct 881 ms 147332 KB Output is correct
8 Correct 807 ms 147200 KB Output is correct
9 Correct 867 ms 146328 KB Output is correct
10 Correct 110 ms 39932 KB Output is correct
11 Correct 890 ms 147140 KB Output is correct
12 Correct 887 ms 146788 KB Output is correct
13 Correct 536 ms 119788 KB Output is correct
14 Correct 886 ms 147408 KB Output is correct
15 Correct 679 ms 121840 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 48236 KB Output is correct
2 Correct 9 ms 18004 KB Output is correct
3 Correct 810 ms 141244 KB Output is correct
4 Correct 886 ms 142324 KB Output is correct
5 Correct 200 ms 60572 KB Output is correct
6 Correct 914 ms 145096 KB Output is correct
7 Correct 883 ms 145908 KB Output is correct
8 Correct 601 ms 118896 KB Output is correct
9 Correct 667 ms 140164 KB Output is correct
10 Correct 630 ms 119244 KB Output is correct
11 Correct 674 ms 143996 KB Output is correct
12 Correct 881 ms 147332 KB Output is correct
13 Correct 807 ms 147200 KB Output is correct
14 Correct 867 ms 146328 KB Output is correct
15 Correct 110 ms 39932 KB Output is correct
16 Correct 890 ms 147140 KB Output is correct
17 Correct 887 ms 146788 KB Output is correct
18 Correct 536 ms 119788 KB Output is correct
19 Correct 886 ms 147408 KB Output is correct
20 Correct 679 ms 121840 KB Output is correct
21 Correct 210 ms 60024 KB Output is correct
22 Correct 1055 ms 140076 KB Output is correct
23 Correct 896 ms 127272 KB Output is correct
24 Correct 1012 ms 137400 KB Output is correct
25 Correct 967 ms 143840 KB Output is correct
26 Correct 944 ms 140264 KB Output is correct
27 Correct 888 ms 133696 KB Output is correct
28 Correct 899 ms 134360 KB Output is correct
29 Correct 1024 ms 138940 KB Output is correct
30 Correct 905 ms 134288 KB Output is correct
31 Correct 948 ms 147300 KB Output is correct
32 Correct 1167 ms 146752 KB Output is correct
33 Correct 761 ms 144020 KB Output is correct
34 Correct 1028 ms 143524 KB Output is correct
35 Correct 840 ms 134460 KB Output is correct