oj.uz

Submission #1069996

# Submission time Handle Problem Language Result Execution time Memory
1069996 2024-08-22T10:54:30 Z juicy 도장 모으기 (JOI14_stamps) C++17
100 / 100
 44 ms 35912 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 3005, inf = 1e9;

int n, t;
int a[N], b[N], lt[N], rt[N], dp[N][N];

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    cin >> n >> t;
    for (int i = 1; i <= n; ++i) {
        int u, v, d, e; cin >> u >> v >> d >> e;
        a[i] = u + v;
        b[i] = d + e;
        rt[i] = u + e + 2 * t * i;
        lt[i] = v + d - 2 * t * i;
    }  
    memset(dp, 0x3f, sizeof(dp));
    dp[0][0] = 0;
    for (int i = 1; i <= n; ++i) {
        int mn = inf;
        for (int j = 0; j <= n; ++j) {
            dp[i][j] =  min(dp[i][j], mn);
            mn = min(mn, dp[i - 1][j]);
            mn = min(inf, mn + lt[i]);
            dp[i][j] = min(dp[i][j], dp[i - 1][j] + a[i]);
            if (j > 0) {
                dp[i][j] = min(dp[i][j], dp[i - 1][j] + b[i]);
            } 
        }
        mn = inf;
        for (int j = n; j >= 0; --j) {
            dp[i][j] = min(dp[i][j], mn);
            mn = min(mn, dp[i - 1][j]);
            mn = min(inf, mn + rt[i]);
        }
    }  
    cout << dp[n][0] + t * (n + 1);
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 35672 KB Output is correct
2 Correct 5 ms 35676 KB Output is correct
3 Correct 4 ms 35672 KB Output is correct
4 Correct 4 ms 35676 KB Output is correct
5 Correct 5 ms 35676 KB Output is correct
6 Correct 4 ms 35676 KB Output is correct
7 Correct 5 ms 35672 KB Output is correct
8 Correct 4 ms 35676 KB Output is correct
9 Correct 4 ms 35784 KB Output is correct
10 Correct 4 ms 35676 KB Output is correct
11 Correct 4 ms 35676 KB Output is correct
12 Correct 4 ms 35676 KB Output is correct
13 Correct 4 ms 35776 KB Output is correct

Subtask #2
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 35676 KB Output is correct
2 Correct 5 ms 35676 KB Output is correct
3 Correct 5 ms 35792 KB Output is correct
4 Correct 5 ms 35676 KB Output is correct
5 Correct 4 ms 35676 KB Output is correct
6 Correct 4 ms 35676 KB Output is correct
7 Correct 4 ms 35788 KB Output is correct
8 Correct 4 ms 35676 KB Output is correct
9 Correct 4 ms 35676 KB Output is correct
10 Correct 5 ms 35768 KB Output is correct
11 Correct 4 ms 35676 KB Output is correct
12 Correct 4 ms 35676 KB Output is correct
13 Correct 4 ms 35676 KB Output is correct
14 Correct 4 ms 35676 KB Output is correct
15 Correct 5 ms 35740 KB Output is correct
16 Correct 5 ms 35672 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 35672 KB Output is correct
2 Correct 5 ms 35672 KB Output is correct
3 Correct 43 ms 35908 KB Output is correct
4 Correct 35 ms 35676 KB Output is correct
5 Correct 27 ms 35912 KB Output is correct
6 Correct 15 ms 35724 KB Output is correct
7 Correct 11 ms 35672 KB Output is correct
8 Correct 44 ms 35676 KB Output is correct
9 Correct 41 ms 35672 KB Output is correct
10 Correct 40 ms 35896 KB Output is correct
11 Correct 42 ms 35672 KB Output is correct
12 Correct 42 ms 35672 KB Output is correct
13 Correct 40 ms 35676 KB Output is correct
14 Correct 41 ms 35676 KB Output is correct
15 Correct 42 ms 35676 KB Output is correct
16 Correct 41 ms 35676 KB Output is correct
17 Correct 44 ms 35672 KB Output is correct