Submission #20485

#	Time	Username	Problem	Language	Result	Execution time	Memory
20485		Lower Boundary (#35)	Can polan into space? (OJUZ11_space)	C++98	11 / 100	1000 ms	10956 KiB

space

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

int n;
bool visited[200001];
long long int cache[301][301];
struct choojin {
	int a[3];
	choojin(int _a, int _b, int _c) {
		a[0] = _a;
		a[1] = _b;
		a[2] = _c;
	}
};
vector<choojin> list;
vector<int> result;
int countNear(int cur) {
	int count = 0;
	for (int i = -1; i < 2; i++) {
		if (i == 0) continue;
		int pos = cur + i;
		if (pos >= 0 && pos < n) {
			if (visited[pos]) count++;
		}
	}
	return count;
}
long long int solve(int cur, int k) {
	if(k != 0) visited[cur] = true;
	if(k == n) return list[cur].a[countNear(cur)];
	long long int ret = 0;
	for (int i = 0; i < n; i++) {
		if (!visited[i]) {
			long long int tmp = ret;
			if(k == 0) ret = max(ret, solve(i, k + 1));
			else ret = max(ret, list[cur].a[countNear(cur)] + solve(i, k + 1));
			if (tmp != ret) cache[cur][k] = i;
			visited[i] = false;
		}
	}
	return ret;
}

void reconstruct(int cur, int k) {
	if (k == n) return;
	result.push_back(cache[cur][k]);
	solve(cache[cur][k], k + 1);
	reconstruct(cache[cur][k], k + 1);
}

int main() {
	memset(cache, -1, sizeof(cache));
	cin >> n;
	for (int i = 0; i < n; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		list.push_back(choojin(a, b, c));
	}
	cout << solve(0, 0) << endl;
	reconstruct(0, 0);
	for (int i = 0; i < result.size(); i++) {
		cout << result[i] + 1 << ' ';
	}
}

Compilation message (stderr)

space.cpp: In function 'int main()':
space.cpp:64:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < result.size(); i++) {
                    ^

• Subtask 1: 11 / 11
• Subtask 2: 0 / 12
• Subtask 3: 0 / 23
• Subtask 4: 0 / 26
• Subtask 5: 0 / 28