oj.uz

Submission #42421

# Submission time Handle Problem Language Result Execution time Memory
42421 2018-02-27T00:32:38 Z nickyrio 도장 모으기 (JOI14_stamps) C++14
100 / 100
 234 ms 80304 KB 
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i<= b; ++i)
#define FORD(i, a, b) for (int i = a; i>=b; --i)
#define REP(i, a) for (int i = 0; i<a; ++i)
#define DEBUG(x) { cerr << #x << " = " << x << endl; }
#define Arr(A, l, r) { cerr << #A  << " = "; FOR(_, l, r) cerr << A[_] << ' '; cerr << endl; }
#define N 3333
#define pp pair<int, int>
#define next __next
#define prev __prev
#define __builtin_popcount __builtin_popcountll
#define bit(S, i) (((S) >> i) & 1)
#define IO ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);

using namespace std;

/* There are 4 cases to get stamps :
    1. Right-right : Up -> Down
    2. Right-left : Up -> Up
    3. Left-right : Down -> Up
    4. Left-left : Down -> Down
*/
// There are no more than N R-R, L-L with optimal solution.
//dp[i][j] : The minimum time to get the i'th station and remain j left-left unpaired.
// Answer is dp[n + 1][0]

void Min(long long &a, long long b) { a = a > b ? b : a; }

int n;
long long t, dp[N][N], u[N], v[N], d[N], e[N];
int main() {
    IO;
    cin >> n >> t;
    FOR(i, 1, n) cin >> u[i] >> v[i] >> d[i] >> e[i];
    //
    FOR(i, 1, n + 1) FOR(j, 0, n) dp[i][j] = 1e18;
    dp[0][0] = 0;
    FOR(i, 0, n) {
        FOR(j, 0, n - 1) {
            if (i && dp[i][j] != 1e18) Min(dp[i][j + 1], dp[i][j] + d[i] + v[i]);
        }
        FORD(j, n, 1) {
            if (i && dp[i][j] != 1e18) Min(dp[i][j - 1], dp[i][j] + u[i] + e[i]);
        }
        FOR(j, 0, n){
            if (dp[i][j] != 1e18) {
                if (i == 0 && j != 0) break;
                //Case R-L
                Min(dp[i + 1][j], dp[i][j] + u[i] + v[i] + t * (2ll * j + 1));
                //Case L-L
                if (i) Min(dp[i + 1][j + 1], dp[i][j] + d[i] + v[i] + t * (2ll * j + 3));
                if (j) {
                    //Case R-R
                    Min(dp[i + 1][j - 1], dp[i][j] + u[i] + e[i] + t * (2ll * j - 1));
                    //Case L-R
                    Min(dp[i + 1][j], dp[i][j] + d[i] + e[i] + t * (2ll * j + 1));
                }
            }
        }
    }
    cout << dp[n + 1][0];
}

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 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 628 KB Output is correct
6 Correct 1 ms 628 KB Output is correct
7 Correct 1 ms 628 KB Output is correct
8 Correct 1 ms 684 KB Output is correct
9 Correct 2 ms 684 KB Output is correct
10 Correct 2 ms 684 KB Output is correct
11 Correct 2 ms 684 KB Output is correct
12 Correct 1 ms 684 KB Output is correct
13 Correct 2 ms 684 KB Output is correct

Subtask #2
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1176 KB Output is correct
2 Correct 1 ms 1176 KB Output is correct
3 Correct 2 ms 1228 KB Output is correct
4 Correct 2 ms 1228 KB Output is correct
5 Correct 2 ms 1228 KB Output is correct
6 Correct 2 ms 1228 KB Output is correct
7 Correct 2 ms 1228 KB Output is correct
8 Correct 2 ms 1312 KB Output is correct
9 Correct 2 ms 1316 KB Output is correct
10 Correct 2 ms 1320 KB Output is correct
11 Correct 2 ms 1324 KB Output is correct
12 Correct 3 ms 1328 KB Output is correct
13 Correct 2 ms 1332 KB Output is correct
14 Correct 2 ms 1336 KB Output is correct
15 Correct 2 ms 1340 KB Output is correct
16 Correct 2 ms 1344 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 79308 KB Output is correct
2 Correct 1 ms 79308 KB Output is correct
3 Correct 192 ms 79376 KB Output is correct
4 Correct 154 ms 79376 KB Output is correct
5 Correct 119 ms 79376 KB Output is correct
6 Correct 58 ms 79376 KB Output is correct
7 Correct 33 ms 79376 KB Output is correct
8 Correct 190 ms 79564 KB Output is correct
9 Correct 197 ms 79636 KB Output is correct
10 Correct 198 ms 79980 KB Output is correct
11 Correct 234 ms 80052 KB Output is correct
12 Correct 197 ms 80052 KB Output is correct
13 Correct 193 ms 80136 KB Output is correct
14 Correct 197 ms 80148 KB Output is correct
15 Correct 194 ms 80304 KB Output is correct
16 Correct 191 ms 80304 KB Output is correct
17 Correct 194 ms 80304 KB Output is correct