JOI 2014/2015 予選 提出ソースコード

joi2014qual1.cpp

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main()
{
	int A, B, C, D, P;
	cin >> A >> B >> C >> D >> P;
	cout << min(A*P, B + (P<=C ? 0 : D*(P-C))) << endl;
	return 0;
}

joi2014qual2.cpp

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main()
{
	int N, M, A[100], B[100] = {};
	cin >> N >> M;
	for (int i = 0; i < M; ++i) {
		int t;
		cin >> t;
		A[i] = t;
	}
	for (int i = 0; i < M; ++i) {
		int o = 0;
		for (int j = 0; j < N; ++j) {
			int t;
			cin >> t;
			o += (t==A[i] ? (++B[j],0) : 1);
		}
		B[A[i]-1] += o;
	}
	for (int i = 0; i < N; ++i) {
		cout << B[i] << endl;
	}
	return 0;
}

joi2014qual3.cpp

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main()
{
	int H,W;
	char M[100][100];
	cin >> H >> W;
	for (int y = 0; y < H; ++y) {
		for (int x = 0; x < W; ++x) {
			cin >> M[x][y];
		}
	}
	for (int y = 0; y < H; ++y) {
		int c = -1;
		for (int x = 0; x < W; ++x) {
			if (M[x][y] == 'c') {
				c = x;
				cout << 0;
			}
			else if (c == -1) {
				cout << -1;
			}
			else {
				cout << x-c;
			}
			if (x < W-1) cout << " ";
		}
		cout << endl;
	}
	return 0;
}
    

joi2014qual4.cpp

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

long long int dp[1000+1][1000+1] = {};
const long long INF = 1e18;
int main()
{
	int N,M,D[1000],C[1000];
	cin >> N >> M;
	for (int i = 0; i < N; ++i) {
		cin >> D[i];
		for (int j = i+1; j <= M; ++j) dp[i][j] = INF;
	}
	for (int i = 0; i < M; ++i) cin >> C[i];
	for (int i = 1; i <= M; ++i) {
		for (int j = 1; j <= min(i,N); ++j) {
			dp[i][j] = min( dp[i-1][j-1] + C[i-1]*D[j-1], dp[i-1][j] );
			//cerr << i << "," << j << ":" << dp[i][j] << endl;
		}
	}
	long long int r = INF;
	for (int i = N; i <= M; ++i) {
		if (dp[i][N] < r) r = dp[i][N];
		//cerr << dp[i][N] << endl;
	}
	cout << r << endl;
	return 0;
}

joi2014qual5.cpp

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

char c[1000][1000];
int t[1000][1000];
bool b[1000][1000];
const long long INF = 1e18;
const int dx[] = {-1,-1,-1,0,1,1,1,0}, dy[] = {-1,0,1,1,1,0,-1,-1};
queue< pair<int,int> > q[2];
int main()
{
	int H,W;
	cin >> H >> W;
	for (int y = 0; y < H; ++y) {
		for (int x = 0; x < W; ++x) {
			cin >> c[x][y];
			if (x > 0) {
				if (c[x-1][y] == '.') ++t[x][y];
				if (c[x][y] == '.') { ++t[x-1][y];  }
			}
			if (y > 0) {
				if (x+1 < W && c[x+1][y-1] == '.') ++t[x][y];
				if (c[x][y-1] == '.') ++t[x][y];
				if (c[x][y] == '.') ++t[x][y-1];
				if (x+1 < W && c[x][y] == '.') ++t[x+1][y-1];
			}
			if (x > 0 && y > 0) {
				if (c[x-1][y-1] == '.') ++t[x][y];
				if (c[x][y] == '.') ++t[x-1][y-1];
			}
			if (x > 0 && y > 0 && c[x-1][y-1] != '.' && t[x-1][y-1] >= c[x-1][y-1]-'0') {
				q[0].push( make_pair(x-1, y-1) );
				b[x-1][y-1] = true;
			}
		}
	}
	long long int z = 0, u = 0, v = 1;
	while (!q[u].empty()) {
		while (!q[u].empty()) {
			int xx = q[u].front().first, yy = q[u].front().second;
			q[u].pop();
			b[xx][yy] = true;
			c[xx][yy] = '.';
			for (int i = 0; i < 8; ++i) {
				if (0 < xx+dx[i] && xx+dx[i] < W && 0 < yy+dy[i] && yy+dy[i] < H) {
					++t[xx+dx[i]][yy+dy[i]];
					if (!b[xx+dx[i]][yy+dy[i]] && c[xx+dx[i]][yy+dy[i]] != '.' && t[xx+dx[i]][yy+dy[i]] >= c[xx+dx[i]][yy+dy[i]]-'0') {
						q[v].push( make_pair(xx+dx[i], yy+dy[i]) );
						b[xx+dx[i]][yy+dy[i]] = true;
					}
				}
			}
		}
		++z;
		swap(u,v);
	}
	cout << z << endl;
	return 0;
}