oj.uz

Submission #115665

# Submission time Handle Problem Language Result Execution time Memory
115665 2019-06-08T14:21:29 Z ckodser Robots (APIO13_robots) C++14
60 / 100
 530 ms 163840 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};
const ll maxm=1e5+500;

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];


inline ll getid(ll a,ll b){
	return a*maxn+b;
}
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);
	}
}


vector<ll> stk[maxm];

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<h;i++){
		for(ll j=0;j<w;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;
			ll sz=0;
			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++){//////////////////////////// 120*n*m
					res=min(res,dp[u][l][z]+dp[u][z+1][r]);
				}
				if(res!=inf){
					stk[res].pb(u);
					sz++;
				}
			}
			for(ll w=0;sz!=0;w++){
				while(stk[w].size()){
					ll v=stk[w].back();
					stk[w].pop_back();
					sz--;
					if(dp[v][l][r]>w){
						dp[v][l][r]=w;
						for(auto e:inp[v]){
							if(dp[e][l][r]==inf){
								stk[w+1].pb(e);
								sz++;
							}
						}
					}
				}
			}
		}
	}
	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 112 ms 135032 KB Output is correct
2 Correct 114 ms 135288 KB Output is correct
3 Correct 112 ms 135012 KB Output is correct
4 Correct 108 ms 135000 KB Output is correct
5 Correct 109 ms 135080 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 135032 KB Output is correct
2 Correct 114 ms 135288 KB Output is correct
3 Correct 112 ms 135012 KB Output is correct
4 Correct 108 ms 135000 KB Output is correct
5 Correct 109 ms 135080 KB Output is correct
6 Correct 109 ms 135064 KB Output is correct
7 Correct 117 ms 134972 KB Output is correct
8 Correct 107 ms 135208 KB Output is correct
9 Correct 111 ms 135032 KB Output is correct
10 Correct 106 ms 135024 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 135032 KB Output is correct
2 Correct 114 ms 135288 KB Output is correct
3 Correct 112 ms 135012 KB Output is correct
4 Correct 108 ms 135000 KB Output is correct
5 Correct 109 ms 135080 KB Output is correct
6 Correct 109 ms 135064 KB Output is correct
7 Correct 117 ms 134972 KB Output is correct
8 Correct 107 ms 135208 KB Output is correct
9 Correct 111 ms 135032 KB Output is correct
10 Correct 106 ms 135024 KB Output is correct
11 Correct 366 ms 143440 KB Output is correct
12 Correct 133 ms 140344 KB Output is correct
13 Correct 218 ms 140092 KB Output is correct
14 Correct 530 ms 144816 KB Output is correct
15 Correct 289 ms 140920 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 135032 KB Output is correct
2 Correct 114 ms 135288 KB Output is correct
3 Correct 112 ms 135012 KB Output is correct
4 Correct 108 ms 135000 KB Output is correct
5 Correct 109 ms 135080 KB Output is correct
6 Correct 109 ms 135064 KB Output is correct
7 Correct 117 ms 134972 KB Output is correct
8 Correct 107 ms 135208 KB Output is correct
9 Correct 111 ms 135032 KB Output is correct
10 Correct 106 ms 135024 KB Output is correct
11 Correct 366 ms 143440 KB Output is correct
12 Correct 133 ms 140344 KB Output is correct
13 Correct 218 ms 140092 KB Output is correct
14 Correct 530 ms 144816 KB Output is correct
15 Correct 289 ms 140920 KB Output is correct
16 Runtime error 397 ms 163840 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Halted 0 ms 0 KB -