JOI2016 予選

最後のJOI予選、やるだけセットやったのに誤読で時間消費してデバッグギリギリ間に合わんかった。
しかもバグは2箇所!が|になってただけ。クソクソクソクソ。死にたい。

本選、春まで死ぬ気で問題解きまくる。
予選満点ちゃうかっても代表にはなったるからな。

1

int main(){
	vector<int> a(4),b(2);
	for(int i=0;i<4;i++)scanf("%d",&a[i]);
	for(int i=0;i<2;i++)scanf("%d",&b[i]);
	sort(all(a),greater<int>());
	sort(all(b),greater<int>());
	int ans = 0;
	for(int i=0;i<3;i++)ans += a[i];
	ans += b[0];
	printf("%d\n",ans);
	return 0;
}

2

int N,M;
int A[105];
int main(){
	scanf("%d %d",&N,&M);
	for(int i=0;i<N;i++)scanf("%d",&A[i]);
	for(int i=1;i<=M;i++){
		for(int j=0;j<N-1;j++){
			if(A[j]%i>A[j+1]%i)swap(A[j],A[j+1]);
		}
	}
	for(int i=0;i<N;i++)printf("%d\n",A[i]);
	return 0;
}

3

int N,M;
string s[55];
int culc(int u,int d){
	int res = 0;
	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++){
			if(i<=u&&s[i][j]!='W')res++;
			if(i>u&&i<=d&&s[i][j]!='B')res++;
			if(i>d&&s[i][j]!='R')res++;
		}
	}
	return res;
}
int main(){
	scanf("%d %d",&N,&M);
	for(int i=0;i<N;i++)cin >> s[i];
	int ans = INF;
	for(int i=0;i<N-2;i++){
		for(int j=i+1;j<N-1;j++){
			ans = min(ans,culc(i,j));
		}
	}
	printf("%d\n",ans);
	return 0;
}

4

int N,Q,D[100100],X[1010];
ll T,A[100100];
int east[100100],west[100100];
int main(){
	scanf("%d %lld %d",&N,&T,&Q);
	memset(east,-1,sizeof(east));
	memset(west,-1,sizeof(west));
	for(int i=0;i<N;i++){
		scanf("%lld %d",&A[i],&D[i]);
		if(D[i]==1)east[i]=i;
		else west[i]=i;
	}
	for(int i=1;i<N;i++)east[i]=(east[i]==-1)?east[i-1]:east[i];
	for(int i=N-2;i>=0;i--)west[i]=(west[i]==-1)?west[i+1]:west[i];
	//for(int i=0;i<N;i++)printf("%d%c",east[i],(i==N-1)?'\n':' ');
	//for(int i=0;i<N;i++)printf("%d%c",west[i],(i==N-1)?'\n':' ');
	for(int i=0;i<Q;i++){
		scanf("%d",&X[i]);
		X[i]--;
	}
	for(int i=0;i<Q;i++){
		if(D[X[i]]==1){
			int a = west[X[i]];
			if(a==-1){
				printf("%lld\n",A[X[i]]+T);
				continue;
			}
			int b = east[a];
			ll crash = A[a]/2ll+A[b]/2ll;
			printf("%lld\n",min(A[X[i]]+T,crash));
		}else{
			int a = east[X[i]];
			if(a==-1){
				printf("%lld\n",A[X[i]]-T);
				continue;
			}
			int b = west[a];
			ll crash = A[a]/2ll+A[b]/2ll;
			printf("%lld\n",max(A[X[i]]-T,crash));
		}
	}
	return 0;
}

5

int N,M,K,S;
ll p,q;
int C[100100];
vector<int> g[100100];
struct edge{
	int to;
	ll cost;
	edge(int to,ll cost):to(to),cost(cost){}
};
vector<edge> G[100100];
int a[200100],b[200100];
ll d[100100];
void dijkstra(){
	for(int i=0;i<N;i++)d[i]=INF;
	priority_queue<P,vector<P>,greater<P> > q;
	for(int i=0;i<K;i++){
		d[C[i]]=0;
		q.push(P(0,C[i]));
	}
	while(!q.empty()){
		P a = q.top();
		q.pop();
		int v = a.sec;
		if(d[v]<a.fi)continue;
		for(int i=0;i<g[v].size();i++){
			int to = g[v][i];
			if(d[to]>d[v]+1){
				d[to]=d[v]+1;
				q.push(P(d[to],to));
			}
		}
	}
	/*for(int i=0;i<N;i++)printf("%d ",d[i]);
	printf("\n");*/
}
ll D[100100];
void dijkstra2(){
	for(int i=0;i<N;i++)D[i]=LLINF;
	priority_queue<P,vector<P>,greater<P> > Q;
	Q.push(P(0ll,0));
	D[0]=0ll;
	while(!Q.empty()){
		P a = Q.top();
		Q.pop();
		int v = a.sec;
		if(D[v]<a.fi)continue;
		for(int i=0;i<G[v].size();i++){
			edge e = G[v][i];
			if(D[e.to]>D[v]+e.cost){
				D[e.to]=D[v]+e.cost;
				Q.push(P(D[e.to],e.to));
			}
		}
	}
}
int main(){
	scanf("%d %d %d %d",&N,&M,&K,&S);
	scanf("%lld %lld",&p,&q);
	for(int i=0;i<K;i++){
		scanf("%d",&C[i]);
		C[i]--;
	}
	for(int i=0;i<M;i++){
		scanf("%d %d",&a[i],&b[i]);
		a[i]--;b[i]--;
		g[a[i]].pb(b[i]);
		g[b[i]].pb(a[i]);
	}
	dijkstra();
	for(int i=0;i<M;i++){
		if(d[a[i]]==0||d[b[i]]==0)continue;
		if(d[a[i]]<=S)G[b[i]].pb(edge(a[i],q));
		else G[b[i]].pb(edge(a[i],p));
		if(b[i]==N-1)G[a[i]].pb(edge(b[i],0ll));
		else if(d[b[i]]<=S)G[a[i]].pb(edge(b[i],q));
		else G[a[i]].pb(edge(b[i],p));
	}
	dijkstra2();
	printf("%lld\n",D[N-1]);
	return 0;
}

6

int H,W;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int dp[1050][1050][32];
int f[1050][1050];
int cost(int i,int j,int k,int m){
	int c = 0;
	if(!(k&16))c+=f[i][j];
	if(m!=0)c+=f[i][j+1];
	if(m!=1)c+=f[i+1][j];
	if(m!=2&&!(k&2))c+=f[i][j-1];
	if(m!=3&&!(k&4))c+=f[i-1][j];
	return c;
}
int moved(int k,int m){
	int nk = 0;
	if(k&1)nk|=2;
	nk|=4;
	if(m!=0)nk|=8;
	if(m!=1)nk|=16;
	return nk;
}
int mover(int k,int m){
	int nk = 0;
	if(k&8)nk|=4;
	nk|=2;
	if(m!=1)nk|=1;
	if(m!=0)nk|=16;
	return nk;
}
int main(){
	scanf("%d %d",&H,&W);
	for(int i=0;i<H;i++){
		string s;
		cin >> s;
		for(int j=0;j<W;j++){
			if(s[j]=='.')f[i+1][j+1]=0;
			else f[i+1][j+1]=(int)(s[j]-'0');
		}
	}
	for(int i=1;i<=H;i++)for(int j=1;j<=W;j++)for(int k=0;k<32;k++)dp[i][j][k]=INF;
	dp[1][1][0]=0;
	for(int i=1;i<=H;i++){
		for(int j=1;j<=W;j++){
			//printf("%d %d : ",i,j);
			for(int k=0;k<32;k++){
				if(dp[i][j][k]==INF)continue;
				//printf("%d ",dp[i][j][k]);
				for(int m=0;m<4;m++){
					int c = cost(i,j,k,m);
					int dk = moved(k,m);
					int rk = mover(k,m);
					//if(i==1)printf("%d %d %d\n",c,dk,rk);
					dp[i+1][j][dk]=min(dp[i+1][j][dk],dp[i][j][k]+c);
					dp[i][j+1][rk]=min(dp[i][j+1][rk],dp[i][j][k]+c);
				}
			}
			//printf("\n");	
		}
	}
	int ans = INF;
	for(int i=0;i<32;i++)ans=min(ans,dp[H][W][i]);
	printf("%d\n",ans);
	return 0;
}