oj.uz

Submission #115674

# Submission time Handle Problem Language Result Execution time Memory
115674 2019-06-08T14:37:56 Z ckodser Robots (APIO13_robots) C++14
100 / 100
 742 ms 148880 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=501;
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[10][10][maxn*maxn];


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);
	}
}



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[l][r][i]=inf;



	for(ll t=1;t<=n;t++){
		for(ll l=0;l+t-1<n;l++){
			ll r=l+t-1;
			vector<pii> vecc;
			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[l][z][u]+dp[z+1][r][u]);
				}
				if(res!=inf){
					vecc.pb(mp(res,u));
				}
			}
			stack<ll> stk,stkk;
			sort(vecc.begin(),vecc.end());
			reverse(vecc.begin(),vecc.end());
			for(ll w=0;vecc.size() || stk.size();w++){
				while(vecc.size() && vecc.back().F==w){
					stk.push(vecc.back().S);
					vecc.pop_back();
				}
				while(stk.size()){
					ll v=stk.top();
					stk.pop();
					if(dp[l][r][v]>w){
						dp[l][r][v]=w;
						for(auto e:inp[v]){
							if(dp[l][r][e]==inf){
								stkk.push(e);
							}
						}
					}
				}
				swap(stk,stkk);
			}
		}
	}
	ll ans=inf;
	for(ll i=0;i<h;i++)for(ll j=0;j<w;j++){
		ans=min(ans,dp[0][n-1][getid(i,j)]);
	}
	if(ans==inf){
		cout<<-1;
	}else{
		cout<<ans;
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 109432 KB Output is correct
2 Correct 116 ms 109428 KB Output is correct
3 Correct 115 ms 109432 KB Output is correct
4 Correct 125 ms 109516 KB Output is correct
5 Correct 125 ms 109404 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 109432 KB Output is correct
2 Correct 116 ms 109428 KB Output is correct
3 Correct 115 ms 109432 KB Output is correct
4 Correct 125 ms 109516 KB Output is correct
5 Correct 125 ms 109404 KB Output is correct
6 Correct 118 ms 109452 KB Output is correct
7 Correct 120 ms 109432 KB Output is correct
8 Correct 121 ms 109408 KB Output is correct
9 Correct 117 ms 109448 KB Output is correct
10 Correct 118 ms 109432 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 109432 KB Output is correct
2 Correct 116 ms 109428 KB Output is correct
3 Correct 115 ms 109432 KB Output is correct
4 Correct 125 ms 109516 KB Output is correct
5 Correct 125 ms 109404 KB Output is correct
6 Correct 118 ms 109452 KB Output is correct
7 Correct 120 ms 109432 KB Output is correct
8 Correct 121 ms 109408 KB Output is correct
9 Correct 117 ms 109448 KB Output is correct
10 Correct 118 ms 109432 KB Output is correct
11 Correct 220 ms 114664 KB Output is correct
12 Correct 134 ms 114288 KB Output is correct
13 Correct 161 ms 114396 KB Output is correct
14 Correct 347 ms 115348 KB Output is correct
15 Correct 174 ms 114620 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 109432 KB Output is correct
2 Correct 116 ms 109428 KB Output is correct
3 Correct 115 ms 109432 KB Output is correct
4 Correct 125 ms 109516 KB Output is correct
5 Correct 125 ms 109404 KB Output is correct
6 Correct 118 ms 109452 KB Output is correct
7 Correct 120 ms 109432 KB Output is correct
8 Correct 121 ms 109408 KB Output is correct
9 Correct 117 ms 109448 KB Output is correct
10 Correct 118 ms 109432 KB Output is correct
11 Correct 220 ms 114664 KB Output is correct
12 Correct 134 ms 114288 KB Output is correct
13 Correct 161 ms 114396 KB Output is correct
14 Correct 347 ms 115348 KB Output is correct
15 Correct 174 ms 114620 KB Output is correct
16 Correct 489 ms 148880 KB Output is correct
17 Correct 742 ms 124812 KB Output is correct
18 Correct 270 ms 123728 KB Output is correct
19 Correct 286 ms 122872 KB Output is correct
20 Correct 590 ms 124484 KB Output is correct