oj.uz

Submission #156049

# Submission time Handle Problem Language Result Execution time Memory
156049 2019-10-03T03:04:32 Z atoiz 도장 모으기 (JOI14_stamps) C++14
0 / 100
 84 ms 47864 KB 
#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 3007;
const long long INF = 1e15;
int n;
long long u[MAXN], v[MAXN], d[MAXN], e[MAXN], t, f[MAXN][MAXN];
void upd(long long &x, long long y) { if (x > y) x = y; }

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> t;
    for (int i = 1; i <= n; ++i) cin >> u[i] >> v[i] >> d[i] >> e[i];
    for (int i = 1; i <= n + 1; ++i) for (int j = 0; j <= n / 2; ++j) f[i][j] = INF;
    f[1][0] = 0;

    for (int i = 1; i <= n; ++i) {
        for (int j = min(i - 1, n / 2); j > 0; --j) if (f[i][j] < INF) upd(f[i][j - 1], f[i][j] + u[i] + e[i]);
        for (int j = 0; j < min(i - 1, n / 2); ++j) if (f[i][j] < INF) upd(f[i][j + 1], f[i][j] + d[i] + v[i]);

        for (int j = min(i - 1, n / 2); j >= 0; --j) if (f[i][j] < INF) {
            upd(f[i + 1][j], f[i][j] + u[i] + v[i] + j * t * 2);
            upd(f[i + 1][j + 1], f[i][j] + d[i] + v[i] + (j + 1) * t * 2);
            if (j > 0) upd(f[i + 1][j], f[i][j] + d[i] + e[i] + j * t * 2);
            if (j > 0) upd(f[i + 1][j - 1], f[i][j] + u[i] + e[i] + (j - 1) * t * 2);
        }
    }
    cout << f[n + 1][0] + t * (n + 1) << endl;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 424 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 504 KB Output is correct
13 Incorrect 2 ms 376 KB Output isn't correct

Subtask #2
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 760 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 636 KB Output is correct
7 Correct 2 ms 760 KB Output is correct
8 Correct 2 ms 764 KB Output is correct
9 Correct 2 ms 760 KB Output is correct
10 Correct 2 ms 760 KB Output is correct
11 Correct 3 ms 888 KB Output is correct
12 Correct 2 ms 760 KB Output is correct
13 Correct 2 ms 760 KB Output is correct
14 Correct 2 ms 888 KB Output is correct
15 Incorrect 2 ms 888 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 47608 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 77 ms 47736 KB Output is correct
4 Correct 62 ms 38520 KB Output is correct
5 Correct 50 ms 30840 KB Output is correct
6 Correct 26 ms 15352 KB Output is correct
7 Correct 19 ms 10204 KB Output is correct
8 Correct 84 ms 47580 KB Output is correct
9 Correct 69 ms 47736 KB Output is correct
10 Correct 77 ms 47740 KB Output is correct
11 Correct 72 ms 47736 KB Output is correct
12 Correct 69 ms 47708 KB Output is correct
13 Correct 69 ms 47712 KB Output is correct
14 Correct 77 ms 47864 KB Output is correct
15 Incorrect 69 ms 47736 KB Output isn't correct
16 Halted 0 ms 0 KB -