oj.uz

Submission #156105

# Submission time Handle Problem Language Result Execution time Memory
156105 2019-10-03T11:40:29 Z Flying_dragon_02 도장 모으기 (JOI14_stamps) C++17
100 / 100
 291 ms 212484 KB 
#include <bits/stdc++.h>

using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;

const int mod = 1e9 + 7;

const int inf = 1e16;

const int N = 3005;

int add(int x, int y) {
    return (1ll * x + 1ll * y) % mod;
}

int del(int x, int y) {
    return ((1ll * x - 1ll * y) % mod + mod) % mod;
}

int mul(int x, int y) {
    return (1ll * x * 1ll * y) % mod;
}

int dp[N][N], n, t, u[N], v[N], d[N], e[N], f[N][N], f1[N][N];

signed main() {
    cin.tie(0), ios_base::sync_with_stdio(0);
    cin >> n >> t;
    for(int i = 1; i <= n; i++)
        cin >> u[i] >> v[i] >> d[i] >> e[i];
    //u[i] = nha cho len doc den cot tem
    //v[i] = cot tem den nha cho tau len doc
    //d[i] = nha cho tau xuong doc den cot tem
    //e[i] = cot tem den nha tau xuong doc
    for(int i = 0; i <= n + 1; i++) {
        for(int j = 0; j <= n + 1; j++) {
            dp[i][j] = inf;

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

/*4 1
1 1 1 1
1 9 9 1
9 9 1 1
1 9 9 1*/

Subtask #1
10.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 632 KB Output is correct
4 Correct 2 ms 632 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 2 ms 632 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Correct 3 ms 632 KB Output is correct
12 Correct 2 ms 632 KB Output is correct
13 Correct 2 ms 632 KB Output is correct

Subtask #2
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1656 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 1788 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 3 ms 1144 KB Output is correct
7 Correct 3 ms 1656 KB Output is correct
8 Correct 3 ms 1784 KB Output is correct
9 Correct 3 ms 1784 KB Output is correct
10 Correct 4 ms 1912 KB Output is correct
11 Correct 4 ms 1912 KB Output is correct
12 Correct 4 ms 1784 KB Output is correct
13 Correct 3 ms 1788 KB Output is correct
14 Correct 3 ms 1912 KB Output is correct
15 Correct 4 ms 1784 KB Output is correct
16 Correct 6 ms 1784 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 212040 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 276 ms 212344 KB Output is correct
4 Correct 232 ms 187384 KB Output is correct
5 Correct 187 ms 155212 KB Output is correct
6 Correct 84 ms 72184 KB Output is correct
7 Correct 52 ms 45532 KB Output is correct
8 Correct 273 ms 212116 KB Output is correct
9 Correct 279 ms 212148 KB Output is correct
10 Correct 275 ms 212220 KB Output is correct
11 Correct 277 ms 212344 KB Output is correct
12 Correct 282 ms 212304 KB Output is correct
13 Correct 283 ms 212484 KB Output is correct
14 Correct 274 ms 212344 KB Output is correct
15 Correct 273 ms 212444 KB Output is correct
16 Correct 274 ms 212412 KB Output is correct
17 Correct 276 ms 212344 KB Output is correct