Submission #42421

#	Time	Username	Problem	Language	Result	Execution time	Memory
42421		nickyrio	도장 모으기 (JOI14_stamps)	C++14	100 / 100	234 ms	80304 KiB

stamps

#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 / 10
• Subtask 2: 75 / 75
• Subtask 3: 15 / 15