제출 #1148012

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1148012		tito_daynor	Coin Collecting (JOI19_ho_t4)	C++17	0 / 100	0 ms	324 KiB

joi2019_ho_t4

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

class CoinCollector {
private:
    int N;
    vector<vector<ll>> dp;
    vector<vector<ll>> coins;

    ll processInitialPosition(ll x, ll y) {
        ll moves = 0;
        
        if (x < 1) {
            moves += 1 - x;
            x = 1;
        } else if (x > N) {
            moves += x - N;
            x = N;
        }
        
        if (y < 1) {
            moves += 1 - y;
            y = 1;
        } else if (y > 2) {
            moves += y - 2;
            y = 2;
        }
        
        coins[x][y-1]++;
        return moves;
    }

    ll calculateMinimumMoves() {
        dp.assign(N + 2, vector<ll>(N + 2, 0));
        
        for (int len = 1; len <= N; len++) {
            for (int i = 1; i + len - 1 <= N; i++) {
                int j = i + len - 1;
                
                ll up = 0, down = 0;
                for (int k = i; k <= j; k++) {
                    up += coins[k][0] - 1;
                    down += coins[k][1] - 1;
                }
                
                if (len == 1) {
                    dp[i][j] = abs(up) + abs(down);
                    if (up > 0 && down < 0) {
                        dp[i][j] += min(up, -down);
                    } else if (up < 0 && down > 0) {
                        dp[i][j] += min(-up, down);
                    }
                } else {
                    dp[i][j] = LLONG_MAX;
                    for (int k = i; k < j; k++) {
                        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + len);
                    }
                }
            }
        }
        
        return dp[1][N];
    }

public:
    ll solve() {
        cin >> N;
        coins.assign(N + 1, vector<ll>(2, 0));
        ll initial_moves = 0;
        
        for (int i = 0; i < 2 * N; i++) {
            ll x, y;
            cin >> x >> y;
            initial_moves += processInitialPosition(x, y);
        }
        
        return initial_moves + calculateMinimumMoves();
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    CoinCollector solver;
    cout << solver.solve() << endl;
    
    return 0;
}

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