oj.uz

답안 #361526

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
361526 2021-01-30T12:07:15 Z Lam_lai_cuoc_doi 도장 모으기 (JOI14_stamps) C++17
100 / 100
 83 ms 71296 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

const bool typetest = 0;
const int N = 3e3 + 5;
const ll Inf = 1e17;
int n;
ll t, stayleft[N], stayright[N], toleft[N], toright[N];
ll dp[N][N];

void Read()
{
    cin >> n >> t;
    for (int i = 1; i <= n; ++i)
    {
        ll rtop, ptor, ltop, ptol;
        cin >> rtop >> ptor >> ltop >> ptol;
        stayleft[i] = ltop + ptol;
        stayright[i] = rtop + ptor;
        toleft[i] = rtop + ptol;
        toright[i] = ltop + ptor;
    }
}

void Min(ll &x, ll y)
{
    if (x > y)
        x = y;
}

void Solve()
{
    fill_n(&dp[0][0], N * N, Inf);
    dp[1][0] = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= n; ++j)
        {
            /// Create a new cycle - Not guarantee that we go throught i-th tramp
            if (j > 0)
                Min(dp[i][j], dp[i][j - 1] + toright[i] - 2 * i * t);
            /// guarantee we go throught i-th tramp
            // End a cycle here
            if (j > 0)
                Min(dp[i + 1][j - 1], dp[i][j] + toleft[i] + 2 * t * i);
            //still go to right
            Min(dp[i + 1][j], dp[i][j] + stayright[i]);
            //go througt a cycle
            Min(dp[i + 1][j + 1], dp[i][j] + toright[i] - 2 * i * t);
            // still go to left (only j > 0)
            if (j > 0)
                Min(dp[i + 1][j], dp[i][j] + stayleft[i]);
        }
    cout << dp[n + 1][0] + (n + 1) * t;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t(1);
    if (typetest)
        cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        Read();
        Solve();
    }
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 71148 KB Output is correct
2 Correct 38 ms 71020 KB Output is correct
3 Correct 38 ms 71020 KB Output is correct
4 Correct 38 ms 71148 KB Output is correct
5 Correct 37 ms 71020 KB Output is correct
6 Correct 37 ms 71040 KB Output is correct
7 Correct 37 ms 71020 KB Output is correct
8 Correct 37 ms 71040 KB Output is correct
9 Correct 37 ms 71020 KB Output is correct
10 Correct 37 ms 71020 KB Output is correct
11 Correct 37 ms 71020 KB Output is correct
12 Correct 37 ms 71020 KB Output is correct
13 Correct 37 ms 71020 KB Output is correct

Subtask #2
75.0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 71020 KB Output is correct
2 Correct 38 ms 71020 KB Output is correct
3 Correct 37 ms 71020 KB Output is correct
4 Correct 38 ms 71040 KB Output is correct
5 Correct 37 ms 71020 KB Output is correct
6 Correct 37 ms 71020 KB Output is correct
7 Correct 38 ms 71148 KB Output is correct
8 Correct 38 ms 71020 KB Output is correct
9 Correct 38 ms 71020 KB Output is correct
10 Correct 37 ms 71020 KB Output is correct
11 Correct 39 ms 71020 KB Output is correct
12 Correct 38 ms 71020 KB Output is correct
13 Correct 38 ms 71020 KB Output is correct
14 Correct 39 ms 71052 KB Output is correct
15 Correct 38 ms 71020 KB Output is correct
16 Correct 39 ms 71020 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 81 ms 71296 KB Output is correct
2 Correct 38 ms 71020 KB Output is correct
3 Correct 83 ms 71148 KB Output is correct
4 Correct 72 ms 71148 KB Output is correct
5 Correct 67 ms 71252 KB Output is correct
6 Correct 49 ms 71024 KB Output is correct
7 Correct 44 ms 71020 KB Output is correct
8 Correct 82 ms 71296 KB Output is correct
9 Correct 78 ms 71148 KB Output is correct
10 Correct 81 ms 71148 KB Output is correct
11 Correct 80 ms 71148 KB Output is correct
12 Correct 77 ms 71148 KB Output is correct
13 Correct 77 ms 71148 KB Output is correct
14 Correct 80 ms 71148 KB Output is correct
15 Correct 77 ms 71148 KB Output is correct
16 Correct 79 ms 71148 KB Output is correct
17 Correct 81 ms 71276 KB Output is correct