제출 #208100

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
208100		ToMmyDong	Coin Collecting (JOI19_ho_t4)	C++11	37 / 100	119 ms	40544 KiB

joi2019_ho_t4

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define REP(i,n) for(int i=0;i<n;++i)
#define REP1(i,n) for(int i=1;i<=n;++i)
#define SZ(i) int(i.size())
#define eb emplace_back
#define ALL(i) i.begin(),i.end()
#define X first
#define Y second
#ifdef tmd
#define IOS()
#define debug(...) fprintf(stderr,"#%d: %s = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
template<typename It> ostream& _printRng(ostream &os,It bg,It ed)
{
    os<<"{";
    for(It it=bg;it!=ed;it++) {
        os<<(it==bg?"":",")<<*it;
    }
    os<<"}";
    return os;
}
template<typename T> ostream &operator << (ostream &os,vector<T> &v){return _printRng(os,v.begin(), v.end());}
template<typename T> void pary(T bg, T ed){_printRng(cerr,bg,ed);cerr<<endl;}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define debug(...)
#define pary(...)
#endif

const int MAXN = 1003;
const ll MOD = 1000000007;

int n;
vector<pll> pos;

void solve (vector<int> x, ll &res) {
    sort(ALL(x));

    for (int i=1; i<=n; i++) {
        res += abs(x[i-1] - i);
    }
}

ll dp[MAXN*2][MAXN];

void ckmin (ll &x, ll y) {
    x = x > y ? y : x;
}
/*********************GoodLuck***********************/
int main () {
    IOS();

    cin >> n;

    REP (i, n*2) {
        int x, y;
        cin >> x >> y;
        pos.eb(x, y);
    }

    sort(ALL(pos));

    memset(dp, 0x3f, sizeof(dp));
    dp[0][0] = 0;

    for (int i=1; i<=n*2; i++) {
        for (int u=0; u<=min(i,n); u++) {
            int d = i-u;
            if (d < 0 || d > n) {
                continue;
            }

            if (d > 0) {
                ckmin(dp[i][u],dp[i-1][u] + abs(pos[i-1].X - d) + abs(pos[i-1].Y - 1));
            }

            if (u > 0) {
                ckmin(dp[i][u],dp[i-1][u-1] + abs(pos[i-1].X - u) + abs(pos[i-1].Y - 2));
            }

            debug(i, u, d, dp[i][u]);
        }
    }

    cout << dp[n*2][n] << endl;
}

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