Submission #522653

#	Time	Username	Problem	Language	Result	Execution time	Memory
522653		Monarchuwu	Coin Collecting (JOI19_ho_t4)	C++17	37 / 100	26 ms	23036 KiB

joi2019_ho_t4

/*
duyệt từ trái sang
đặt x là lượng coin có được
    x1 là lượng coin hàng trên

dp[x1] là state có x1 coin hàng trên và x - x1 coin hàng dưới
nếu thêm 1 coin hàng trên : dp[x - 1][i] -> dp[x][i + 1]
nếu thêm 1 coin hàng dưới : dp[x - 1][i] -> dp[x][i]
*/
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;

typedef pair<int, int> pii;
#define ff first
#define ss second

const ll inf = 1e18;
const int N = 2000 + 3;
int n;
pii p[N];

ll dp[N][N];
int dist(pii a, pii b) {
    return abs(a.ff - b.ff) + abs(a.ss - b.ss);
}
int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n * 2; ++i) cin >> p[i].ff >> p[i].ss;

    sort(p + 1, p + n * 2 + 1);
    ll sum(0);
    for (int i = 1; i <= n * 2; ++i) {
        fill(dp[i], dp[i] + i + 1, inf);

        if (p[i].ff < 1) {
            sum += 1 - p[i].ff;
            p[i].ff = 1;
        }
        if (n < p[i].ff) {
            sum += p[i].ff - n;
            p[i].ff = n;
        }
        if (p[i].ss < 1) {
            sum += 1 - p[i].ss;
            p[i].ss = 1;
        }
        if (2 < p[i].ss) {
            sum += p[i].ss - 2;
            p[i].ss = 2;
        }

        for (int x = 0; x < i; ++x) {
            // dp[i - 1][x] -> dp[i][x]
            // go to (i - x, 2)
            dp[i][x] = min(dp[i][x], dp[i - 1][x] + dist(p[i], pii(i - x, 2)));

            // dp[i - 1][x] -> dp[i][x + 1]
            // go to (x + 1, 1)
            dp[i][x + 1] = min(dp[i][x + 1], dp[i - 1][x] + dist(p[i], pii(x + 1, 1)));
        }
    }
    cout << sum + dp[n * 2][n] << '\n';
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

• Subtask 1: 8 / 8
• Subtask 2: 29 / 29
• Subtask 3: 0 / 63