oj.uz

Submission #361301

# Submission time Handle Problem Language Result Execution time Memory
361301 2021-01-29T08:23:26 Z RyoPham 도장 모으기 (JOI14_stamps) C++14
100 / 100
 95 ms 35948 KB 
#define taskname "test"

#include <bits/stdc++.h>

using namespace std;

#define sz(x) (int)x.size()
#define fi first
#define se second

typedef long long lli;
typedef pair<int, int> pii;

const int maxn = 3005;
const int inf = 1e9 + 9;

int n, t;
int u[maxn], v[maxn], d[maxn], e[maxn];

int dp[maxn][maxn];

void read_input()
{
    cin >> n >> t;
    for(int i = 1; i <= n; ++i)
        cin >> u[i] >> v[i] >> d[i] >> e[i];
}

void solve()
{
    fill_n(&dp[0][0], sizeof(dp) / sizeof(dp[0][0]), inf);
    dp[1][0] = 0;
    for(int i = 1; i <= n; ++i)
        for(int j = 0; j <= n; ++j)
        {
            if(j > 0) dp[i][j] = min(dp[i][j], dp[i][j - 1] + d[i] + v[i] - 2 * t * i);
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + u[i] + v[i]);
            dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + d[i] + v[i] - 2 * t * i);
            if(j > 0) dp[i + 1][j - 1] = min(dp[i + 1][j - 1], dp[i][j] + u[i] + e[i] + 2 * t * i);
            if(j > 0) dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + d[i] + e[i]);
        }
    cout << (n + 1) * t + dp[n + 1][0] << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    read_input();
    solve();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 35692 KB Output is correct
2 Correct 23 ms 35692 KB Output is correct
3 Correct 24 ms 35692 KB Output is correct
4 Correct 24 ms 35692 KB Output is correct
5 Correct 23 ms 35692 KB Output is correct
6 Correct 23 ms 35692 KB Output is correct
7 Correct 24 ms 35692 KB Output is correct
8 Correct 23 ms 35820 KB Output is correct
9 Correct 24 ms 35692 KB Output is correct
10 Correct 23 ms 35712 KB Output is correct
11 Correct 24 ms 35712 KB Output is correct
12 Correct 23 ms 35692 KB Output is correct
13 Correct 23 ms 35692 KB Output is correct

Subtask #2
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 35692 KB Output is correct
2 Correct 25 ms 35692 KB Output is correct
3 Correct 23 ms 35692 KB Output is correct
4 Correct 24 ms 35712 KB Output is correct
5 Correct 23 ms 35712 KB Output is correct
6 Correct 23 ms 35692 KB Output is correct
7 Correct 23 ms 35692 KB Output is correct
8 Correct 28 ms 35692 KB Output is correct
9 Correct 24 ms 35692 KB Output is correct
10 Correct 23 ms 35692 KB Output is correct
11 Correct 23 ms 35692 KB Output is correct
12 Correct 23 ms 35692 KB Output is correct
13 Correct 23 ms 35692 KB Output is correct
14 Correct 27 ms 35692 KB Output is correct
15 Correct 23 ms 35692 KB Output is correct
16 Correct 23 ms 35692 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 35820 KB Output is correct
2 Correct 24 ms 35692 KB Output is correct
3 Correct 88 ms 35820 KB Output is correct
4 Correct 76 ms 35820 KB Output is correct
5 Correct 63 ms 35820 KB Output is correct
6 Correct 40 ms 35820 KB Output is correct
7 Correct 33 ms 35692 KB Output is correct
8 Correct 88 ms 35820 KB Output is correct
9 Correct 90 ms 35948 KB Output is correct
10 Correct 88 ms 35948 KB Output is correct
11 Correct 92 ms 35820 KB Output is correct
12 Correct 88 ms 35768 KB Output is correct
13 Correct 95 ms 35820 KB Output is correct
14 Correct 91 ms 35820 KB Output is correct
15 Correct 87 ms 35948 KB Output is correct
16 Correct 87 ms 35820 KB Output is correct
17 Correct 95 ms 35820 KB Output is correct