Submission #635132

#	Time	Username	Problem	Language	Result	Execution time	Memory
635132		slime	Coin Collecting (JOI19_ho_t4)	C++14	0 / 100	1 ms	340 KiB

joi2019_ho_t4

#include "bits/stdc++.h"
#define int long long
using namespace std;
 
struct coin {
    int ox, oy; // original x, y
    int nx, ny; // new x, y
    int cost = 0;
};

void solve(int tc) {
    int n;
    cin >> n;
    coin c[2*n + 1];
    for(int i=1; i<=2*n; i++) {
        cin >> c[i].ox >> c[i].oy;
        if(c[i].ox > n) {
            if(c[i].oy >= 2) { // Choose (n, 2)
                c[i].nx = n;
                c[i].ny = 2;
            }
            else { // Choose (n, 1)
                c[i].nx = n;
                c[i].ny = 1;
            }
        }
        else if(c[i].ox < 1) {
            if(c[i].oy >= 2) {
                c[i].nx = 1;
                c[i].ny = 2;
            }
            else {
                c[i].nx = 1;
                c[i].ny = 1;
            }
        }
        else { 
            if(c[i].oy >= 2) {
                c[i].nx = c[i].ox;
                c[i].ny = 2;
            }
            else {
                c[i].nx = c[i].ox;
                c[i].ny = 1;
            }
        }
 
        c[i].cost = abs(c[i].ox - c[i].nx) + abs(c[i].oy - c[i].ny);
    }
    int base = 0;
    for(int i=1; i<=2*n; i++) base += c[i].cost;
    int cnt[n+1][3];
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=2; j++) {
            cnt[i][j] = 0;
        }
    }
 
    for(int i=1; i<=2*n; i++) cnt[c[i].nx][c[i].ny]++;
    
    vector<pair<int, int> > zero, verypos;
    zero.push_back({0, 0});
    verypos.push_back({0, 0});

    for(int i=1; i<=n; i++) {
        for(int j=1; j<=2; j++) {
            if(cnt[i][j] == 0) {
                zero.push_back({i, j});
            }
            else {
                for(int k=0; k<cnt[i][j]-1; k++) {
                    verypos.push_back({i, j});
                }
            }
        }
    }

    int m = zero.size() - 1;

    int dp[m + 1]; 
    for(int i=0; i<=m; i++) dp[i] = 1e18;
    dp[0] = 0;

    for(int i=1; i<=m; i++) {

        for(int j=max(0ll, i-6); j<i; j++) {
            vector<int> perm;
            for(int k=j+1; k<=i; k++) perm.push_back(k);
            int aa = 1e18;
            do {
                int bb = 0;
                int ind = j+1;
                for(int x: perm) {
                    bb += abs(zero[x].first - verypos[ind].first) + abs(zero[x].second - verypos[ind].second);
                    ind++;
                }
                aa = min(aa, bb);
            } while(next_permutation(perm.begin(), perm.end()));
            dp[i] = min(dp[i], dp[j] + aa);
        }
    }
    

    cout << dp[m] + base << "\n";
 
}
int32_t main() {
    int t = 1;
    // cin >> t;
    for(int i=1; i<=t; i++) solve(i);
}

/*
Test case

4
0 2
3 1
3 1
2 1
4 2
0 3
1 0
1 3

*/

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