oj.uz

Submission #115672

# Submission time Handle Problem Language Result Execution time Memory
115672 2019-06-08T14:32:46 Z ckodser Robots (APIO13_robots) C++14
60 / 100
 608 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=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[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);
	}
}



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;
			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[u][l][z]+dp[u][z+1][r]);
				}
				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[v][l][r]>w){
						dp[v][l][r]=w;
						for(auto e:inp[v]){
							if(dp[e][l][r]==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[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 101 ms 128120 KB Output is correct
2 Correct 104 ms 128120 KB Output is correct
3 Correct 106 ms 128108 KB Output is correct
4 Correct 108 ms 128288 KB Output is correct
5 Correct 102 ms 128076 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 128120 KB Output is correct
2 Correct 104 ms 128120 KB Output is correct
3 Correct 106 ms 128108 KB Output is correct
4 Correct 108 ms 128288 KB Output is correct
5 Correct 102 ms 128076 KB Output is correct
6 Correct 102 ms 128044 KB Output is correct
7 Correct 104 ms 128112 KB Output is correct
8 Correct 106 ms 128008 KB Output is correct
9 Correct 102 ms 127992 KB Output is correct
10 Correct 102 ms 128120 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 128120 KB Output is correct
2 Correct 104 ms 128120 KB Output is correct
3 Correct 106 ms 128108 KB Output is correct
4 Correct 108 ms 128288 KB Output is correct
5 Correct 102 ms 128076 KB Output is correct
6 Correct 102 ms 128044 KB Output is correct
7 Correct 104 ms 128112 KB Output is correct
8 Correct 106 ms 128008 KB Output is correct
9 Correct 102 ms 127992 KB Output is correct
10 Correct 102 ms 128120 KB Output is correct
11 Correct 374 ms 133384 KB Output is correct
12 Correct 126 ms 132856 KB Output is correct
13 Correct 225 ms 133016 KB Output is correct
14 Correct 608 ms 133756 KB Output is correct
15 Correct 302 ms 133120 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 128120 KB Output is correct
2 Correct 104 ms 128120 KB Output is correct
3 Correct 106 ms 128108 KB Output is correct
4 Correct 108 ms 128288 KB Output is correct
5 Correct 102 ms 128076 KB Output is correct
6 Correct 102 ms 128044 KB Output is correct
7 Correct 104 ms 128112 KB Output is correct
8 Correct 106 ms 128008 KB Output is correct
9 Correct 102 ms 127992 KB Output is correct
10 Correct 102 ms 128120 KB Output is correct
11 Correct 374 ms 133384 KB Output is correct
12 Correct 126 ms 132856 KB Output is correct
13 Correct 225 ms 133016 KB Output is correct
14 Correct 608 ms 133756 KB Output is correct
15 Correct 302 ms 133120 KB Output is correct
16 Runtime error 398 ms 163840 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Halted 0 ms 0 KB -