제출 #1123459

#제출 시각아이디문제언어결과실행 시간메모리
1123459LucaIlieCoin Collecting (JOI19_ho_t4)C++20
8 / 100
9 ms8264 KiB
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1000;
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";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...