Submission #525510

#	Time	Username	Problem	Language	Result	Execution time	Memory
525510		Lobo	Coin Collecting (JOI19_ho_t4)	C++17	37 / 100	83 ms	25176 KiB

joi2019_ho_t4

#include<bits/stdc++.h>
using namespace std;

const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

#define maxn 1010

int n, mark[maxn][maxn], dp[maxn][maxn];
vector<pair<int,int>> p;

int sol(int i, int j) {
    if(mark[i][j]) return dp[i][j];
    mark[i][j] = 1;
    dp[i][j] = inf;

    int id = i+j;
    if(id == 2*n) {
        return dp[i][j] = 0;
    }
    if(i != n) {
        //pegar com id em cima
        int val = abs(p[id].fr-i-1) + abs(p[id].sc-2);
        dp[i][j] = min(sol(i+1,j)+val,dp[i][j]);
    }

    if(j != n) {
        //pegar com id em cima
        int val = abs(p[id].fr-j-1) + abs(p[id].sc-1);
        dp[i][j] = min(sol(i,j+1)+val,dp[i][j]);
    }

    return dp[i][j];
}

void solve() {
    cin >> n;
    for(int i = 0; i < 2*n; i++) {
        int x, y;
        cin >> x >> y;
        p.pb(mp(x,y));
    }

    sort(all(p));

    cout << sol(0,0) << endl;
    // for(int i = 0; i <= n; i++) {
    //     for(int j = 0; j <= n; j++) {
    //         cout << i << " " << j << " " << sol(i,j) << endl;
    //     }
    // }
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);
    
    int tt = 1;
    // cin >> tt;
    while(tt--) solve();

}

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