제출 #1123460

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1123460		LucaIlie	Coin Collecting (JOI19_ho_t4)	C++20	8 / 100	11 ms	12104 KiB

joi2019_ho_t4

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 3000;
const long long INF = 1e18;
vector<int> a, b;
long long dp[2 * MAX_N + 1][MAX_N + 1];

int main() {
    int n;
    long long ans = 0;

    cin >> n;
    for ( int i = 0; i < 2 * n; i++ ) {
        int x, y;
        cin >> x >> y;
        if ( x < 1 ) {
            ans += 1 - x;
            x = 1;
        } else if ( x > n ) {
            ans += x - n;
            x = n;
        }
        if ( y < 1 ) {
            ans += 1 - y;
            y = 1;
        } else if ( y > 2 ) {
            ans += y - 2;
            y = 2;
        }
        if ( y == 1 )
            a.push_back( x );
        else
            b.push_back( x );
    }
    if ( a.size() > b.size() )
        swap( a, b );
    sort( a.begin(), a.end() );
    sort( b.begin(), b.end() );
    
    for ( int c = 0; c <= n; c++ ) {
        for ( int i = 0; i <= n; i++ )
            dp[c][i] = INF;
    }
    dp[0][0] = 0;
    for ( int c = 1; c <= n; c++ ) {
        for ( int i = 0; i <= c; i++ ) {
            int j = 2 * c - i;
            if ( i <= a.size() && j <= b.size() ) {
                if ( i >= 2 )
                    dp[c][i] = min( dp[c][i], dp[c - 1][i - 2] + abs( a[i - 2] - c ) + abs( a[i - 1] - c ) + 1 );
                if ( i >= 1 && j >= 1 )
                    dp[c][i] = min( dp[c][i], dp[c - 1][i - 1] + abs( a[i - 1] - c ) + abs( b[j - 1] - c ) );
                if ( j >= 2 )
                    dp[c][i] = min( dp[c][i], dp[c - 1][i] + abs( b[j - 2] - c ) + abs( b[j - 1] - c ) + 1 );
            }
        }
    }

    cout << ans + dp[n][a.size()] << "\n";
}

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