oj.uz

Submission #115663

# Submission time Handle Problem Language Result Execution time Memory
115663 2019-06-08T14:08:11 Z ckodser Robots (APIO13_robots) C++14
30 / 100
 1500 ms 139612 KB 
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif


#define ll int
#define pb push_back
#define ld long double
#define mp make_pair
#define F first
#define S second
#define pii pair<ll,ll> 

using namespace :: std;

const ll maxn=510;
const ll inf=1e9+800;

const ll di[4]={-1,0 ,+1,0 };
const ll dj[4]={0 ,+1,0 ,-1};
ll w,h;
string s[maxn];
vector<pair<pii,ll> > out[maxn][maxn][4];
bool good[maxn][maxn][4];


vector<ll> inp[maxn*maxn];
ll dp[maxn*maxn][10][10];


ll getid(ll a,ll b){
	return a*maxn+b;
}
void pri(ll a){
	cout<<a/maxn<<' '<<a%maxn<<" &*& ";
}
ll chimishe(char s,ll d){
	if(s=='C'){
		d=(d+1)%4;
	}if(s=='A'){
		d=(d+3)%4;
	}return d;
}
pair<pii,ll> movein(ll i,ll j,ll d){
	i+=di[d];
	j+=dj[d];
	if(i<0 || i>=h || j<0 || j>=w || s[i][j]=='x'){
		i-=di[d];
		j-=dj[d];
	}
	return mp(mp(i,j),d);
}
void dfs(ll i,ll j,ll d,ll c){
	if(getid(i,j)!=c)
	inp[getid(i,j)].pb(c);
	for(auto e:out[i][j][d]){
		dfs(e.F.F,e.F.S,e.S,c);
	}
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);	
	ll n;
	cin>>n>>w>>h;
	for(ll i=0;i<h;i++){
		cin>>s[i];
	}
	for(ll i=0;i<h;i++){
		for(ll j=0;j<w;j++){
			if('1'<=s[i][j] && s[i][j]<='9'){
				s[i][j]-='1';
			}
		}
	}	
	for(ll i=0;i<h;i++){
		for(ll j=0;j<w;j++){
			if(s[i][j]!='x'){
				for(ll d=0;d<4;d++){
					pair<pii,ll> e=movein(i,j,chimishe(s[i][j],d));
					if(e.F.F==i && e.F.S==j){
						good[i][j][d]=1;
					}else{
						out[e.F.F][e.F.S][e.S].pb(mp(mp(i,j),d));
					}
				}
			}
		}
	}
	for(ll i=0;i<maxn;i++){
		for(ll j=0;j<maxn;j++){
			for(ll d=0;d<4;d++){
				if(good[i][j][d]){
					dfs(i,j,d,getid(i,j));
				}
			}
		}	
	}
	for(ll i=0;i<maxn*maxn;i++)for(ll l=0;l<9;l++)for(ll r=0;r<9;r++)dp[i][l][r]=inf;
	for(ll t=1;t<=n;t++){
		for(ll l=0;l+t-1<n;l++){
			ll r=l+t-1;
			set<pii> st;
			for(ll i=0;i<h;i++)for(ll j=0;j<w;j++){
				ll u=getid(i,j);
				ll res=inf;
				if(t==1 && s[i][j]==l){
					res=0;
				}
				for(ll z=l;z<r;z++){
					res=min(res,dp[u][l][z]+dp[u][z+1][r]);
				}
				if(res!=inf){
					st.insert(mp(res,u));
				}
			}
			while(st.size()){
				pii e=(*st.begin());
				st.erase(e);
				ll v=e.S;
				ll w=e.F;
				if(dp[v][l][r]>w){
					dp[v][l][r]=w;
					for(auto e:inp[v]){
						st.insert(mp(w+1,e));
					}
				}
			}
		}
	}
	ll ans=inf;
	for(ll i=0;i<h;i++)for(ll j=0;j<w;j++){
		ans=min(ans,dp[getid(i,j)][0][n-1]);
	}
	if(ans==inf){
		cout<<-1;
	}else{
		cout<<ans;
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 132728 KB Output is correct
2 Correct 106 ms 132728 KB Output is correct
3 Correct 105 ms 132728 KB Output is correct
4 Correct 118 ms 132712 KB Output is correct
5 Correct 110 ms 132672 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 132728 KB Output is correct
2 Correct 106 ms 132728 KB Output is correct
3 Correct 105 ms 132728 KB Output is correct
4 Correct 118 ms 132712 KB Output is correct
5 Correct 110 ms 132672 KB Output is correct
6 Correct 109 ms 132696 KB Output is correct
7 Correct 110 ms 132648 KB Output is correct
8 Correct 113 ms 132752 KB Output is correct
9 Correct 107 ms 132748 KB Output is correct
10 Correct 111 ms 132728 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 132728 KB Output is correct
2 Correct 106 ms 132728 KB Output is correct
3 Correct 105 ms 132728 KB Output is correct
4 Correct 118 ms 132712 KB Output is correct
5 Correct 110 ms 132672 KB Output is correct
6 Correct 109 ms 132696 KB Output is correct
7 Correct 110 ms 132648 KB Output is correct
8 Correct 113 ms 132752 KB Output is correct
9 Correct 107 ms 132748 KB Output is correct
10 Correct 111 ms 132728 KB Output is correct
11 Correct 643 ms 139000 KB Output is correct
12 Correct 133 ms 137592 KB Output is correct
13 Correct 230 ms 137880 KB Output is correct
14 Execution timed out 1565 ms 139612 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 132728 KB Output is correct
2 Correct 106 ms 132728 KB Output is correct
3 Correct 105 ms 132728 KB Output is correct
4 Correct 118 ms 132712 KB Output is correct
5 Correct 110 ms 132672 KB Output is correct
6 Correct 109 ms 132696 KB Output is correct
7 Correct 110 ms 132648 KB Output is correct
8 Correct 113 ms 132752 KB Output is correct
9 Correct 107 ms 132748 KB Output is correct
10 Correct 111 ms 132728 KB Output is correct
11 Correct 643 ms 139000 KB Output is correct
12 Correct 133 ms 137592 KB Output is correct
13 Correct 230 ms 137880 KB Output is correct
14 Execution timed out 1565 ms 139612 KB Time limit exceeded
15 Halted 0 ms 0 KB -