이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <stdio.h>
#define N 2000
#define M 2000
#define C 50
#define S (N * C)
#define INF 0x3f3f3f3f3f3f3f3fLL
long long max(long long a, long long b) { return a > b ? a : b; }
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int cc[N + M], ff[N + M], vv[N + M];
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k) {
int c = ff[ii[j]] != ff[i_] ? ff[i_] - ff[ii[j]] : ii[j] - i_;
if (c == 0)
j++;
else if (c < 0) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
}
sort(ii, l, i);
l = k;
}
}
int main() {
static int ii[N + M];
static long long dp[S + 1];
int n, m, i, s;
long long ans;
scanf("%d", &n);
for (i = 0; i < n; i++)
scanf("%d%d%d", &cc[i], &ff[i], &vv[i]);
scanf("%d", &m);
for (i = n; i < n + m; i++)
scanf("%d%d%d", &cc[i], &ff[i], &vv[i]);
for (i = 0; i < n + m; i++)
ii[i] = i;
sort(ii, 0, n + m);
for (s = 1; s <= S; s++)
dp[s] = -INF;
dp[0] = 0;
for (i = 0; i < n + m; i++) {
int i_ = ii[i];
if (i_ < n) {
for (s = S; s >= cc[i_]; s--)
if (dp[s - cc[i_]] != -INF)
dp[s] = max(dp[s], dp[s - cc[i_]] - vv[i_]);
} else {
for (s = 0; s + cc[i_] <= S; s++)
if (dp[s + cc[i_]] != -INF)
dp[s] = max(dp[s], dp[s + cc[i_]] + vv[i_]);
}
}
ans = 0;
for (s = 0; s <= S; s++)
ans = max(ans, dp[s]);
printf("%lld\n", ans);
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
clo.c: In function 'main':
clo.c:47:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
47 | scanf("%d", &n);
| ^~~~~~~~~~~~~~~
clo.c:49:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
49 | scanf("%d%d%d", &cc[i], &ff[i], &vv[i]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
clo.c:50:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
50 | scanf("%d", &m);
| ^~~~~~~~~~~~~~~
clo.c:52:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
52 | scanf("%d%d%d", &cc[i], &ff[i], &vv[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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |