제출 #20626

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
20626		Where is my GPA? (#35)	Can polan into space? (OJUZ11_space)	C++14	46 / 100	63 ms	6356 KiB

space

#include <bits/stdc++.h>
using namespace std;

typedef long long lint;

const int maxn = 304;

int n, a[maxn], b[maxn], c[maxn], ans[maxn][maxn][4];
lint m[maxn][maxn][4];

void update(int x, int y, int z, lint k, int p) {
	if (m[x][y][z] < k) {
		m[x][y][z] = k;
		ans[x][y][z] = p;
	}
}

lint dp(int x, int y, int z) {
	if (x>y) return 0;

	lint& ret = m[x][y][z];
	if (ret) return ret;

	update(x, y, z, ((z&1) ? b[x] : a[x]) + dp(x+1, y, (z&2)|1), x);
	update(x, y, z, ((z&2) ? b[y] : a[y]) + dp(x, y-1, (z&1)|2), y);
	for (int i=x+1; i<y; i++) update(x, y, z, dp(x, i-1, (z&1)|2) + a[i] + dp(i+1, y, (z&2)|1), i);

	return ret;
}

void redo(int x, int y, int z) {
	if (x>y) return;

	int now = ans[x][y][z];
	printf("%d ", now+1);
	redo(x, now-1, (z&1)|2);
	redo(now+1, y, (z&2)|1);
}

int main()
{
	scanf("%d", &n);
	for (int i=0; i<n; i++) scanf("%d%d%d", a+i, b+i, c+i);
	c[0] = b[0]; c[n-1] = b[n-1];
	b[0] = a[0]; b[n-1] = a[n-1];

	if (n==1) { printf("%d\n1", a[0]); return 0; }

	for (int i=0; i<n; i++) for (int k=0; k<4; k++) update(i, i, k, c[i], i);

	printf("%lld\n", dp(0, n-1, 0));
	redo(0, n-1, 0);
}

컴파일 시 표준 에러 (stderr) 메시지

space.cpp: In function 'int main()':
space.cpp:42:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
space.cpp:43:56: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i=0; i<n; i++) scanf("%d%d%d", a+i, b+i, c+i);
                                                        ^

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