이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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);
^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |