oj.uz

답안 #156066

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
156066 2019-10-03T06:57:18 Z EntityIT 도장 모으기 (JOI14_stamps) C++14
100 / 100
 279 ms 141952 KB 
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
const LL infLL = (LL)1e18 + 123;
const int N = (int)3e3 + 5;

void assignMin(LL &a, LL b) {
    a = min(a, b);
}

int n, t, u[N], v[N], d[N], e[N];
LL dp[2][N][N];

int main() {
    scanf(" %d %d", &n, &t);
    for (int i = 1; i <= n; ++i) scanf(" %d %d %d %d", u + i, v + i, d + i, e + i);

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) dp[0][i][j] = dp[1][i][j] = infLL;
    }
    dp[0][1][0] = t;
    for (int i = 1; i <= n; ++i) {
        for (int j = n; j > 0; --j) assignMin(dp[1][i][j - 1], dp[0][i][j] + u[i] + e[i]);
        for (int j = n; j > 0; --j) assignMin(dp[1][i][j - 1], dp[1][i][j] + u[i] + e[i]);
        for (int j = 0; j < n; ++j) assignMin(dp[1][i][j + 1], dp[0][i][j] + d[i] + v[i]);
        for (int j = 0; j < n; ++j) assignMin(dp[1][i][j + 1], dp[1][i][j] + d[i] + v[i]);
        for (int j = 0; j <= n; ++j) {
            assignMin(dp[1][i][j], dp[0][i][j] + u[i] + v[i]);
            if (j) assignMin(dp[1][i][j], dp[0][i][j] + d[i] + e[i]);
        }
        for (int j = 0; j <= n; ++j) assignMin(dp[0][i + 1][j], dp[1][i][j] + t + 2 * j * t);
    }

    printf("%lld", dp[1][n][0] + t);

    return 0;
}

Compilation message

stamps.cpp: In function 'int main()':
stamps.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %d %d", &n, &t);
     ~~~~~^~~~~~~~~~~~~~~~~~
stamps.cpp:18:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 1; i <= n; ++i) scanf(" %d %d %d %d", u + i, v + i, d + i, e + i);
                                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 123 ms 141688 KB Output is correct
2 Correct 123 ms 141688 KB Output is correct
3 Correct 124 ms 141660 KB Output is correct
4 Correct 122 ms 141664 KB Output is correct
5 Correct 123 ms 141816 KB Output is correct
6 Correct 125 ms 141672 KB Output is correct
7 Correct 122 ms 141816 KB Output is correct
8 Correct 123 ms 141732 KB Output is correct
9 Correct 121 ms 141688 KB Output is correct
10 Correct 123 ms 141704 KB Output is correct
11 Correct 124 ms 141688 KB Output is correct
12 Correct 123 ms 141736 KB Output is correct
13 Correct 122 ms 141792 KB Output is correct

Subtask #2
75.0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 123 ms 141684 KB Output is correct
2 Correct 121 ms 141636 KB Output is correct
3 Correct 144 ms 141688 KB Output is correct
4 Correct 122 ms 141688 KB Output is correct
5 Correct 123 ms 141688 KB Output is correct
6 Correct 122 ms 141688 KB Output is correct
7 Correct 121 ms 141688 KB Output is correct
8 Correct 122 ms 141816 KB Output is correct
9 Correct 130 ms 141716 KB Output is correct
10 Correct 124 ms 141712 KB Output is correct
11 Correct 122 ms 141688 KB Output is correct
12 Correct 123 ms 141688 KB Output is correct
13 Correct 122 ms 141692 KB Output is correct
14 Correct 135 ms 141672 KB Output is correct
15 Correct 133 ms 141708 KB Output is correct
16 Correct 135 ms 141772 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 216 ms 141816 KB Output is correct
2 Correct 122 ms 141744 KB Output is correct
3 Correct 220 ms 141944 KB Output is correct
4 Correct 199 ms 141816 KB Output is correct
5 Correct 179 ms 141812 KB Output is correct
6 Correct 148 ms 141816 KB Output is correct
7 Correct 139 ms 141740 KB Output is correct
8 Correct 226 ms 141952 KB Output is correct
9 Correct 233 ms 141840 KB Output is correct
10 Correct 222 ms 141880 KB Output is correct
11 Correct 220 ms 141848 KB Output is correct
12 Correct 218 ms 141844 KB Output is correct
13 Correct 218 ms 141820 KB Output is correct
14 Correct 219 ms 141904 KB Output is correct
15 Correct 217 ms 141816 KB Output is correct
16 Correct 228 ms 141812 KB Output is correct
17 Correct 279 ms 141828 KB Output is correct