# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
902514 | jay_jayjay | Coin Collecting (JOI19_ho_t4) | C++17 | 156 ms | 274432 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// {{{1
extern "C" int __lsan_is_turned_off() { return 1; }
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define infl 0x3f3f3f3f3f3f3f3fll
#include <assert.h>
#ifdef DEBUG
#define dprintf(args...) fprintf(stderr,args)
#endif
#ifndef DEBUG
#define dprintf(args...) 69
#endif
#define all(x) (x).begin(), (x).end()
// 1}}}
void chmin(ll& x, ll y) { x=min(x,y); }
int dist(array<int,2> a, array<int,2> b) {
return abs(a[0]-b[0])+abs(a[1]-b[1]);
}
int main()
{
int n;scanf("%d",&n);
vector<array<int,2>> coins(2*n);
for(auto&[x,y]:coins)scanf("%d%d",&x,&y);
sort(all(coins));
vector dp(n+1, vector<ll>(n+1,infl));
dp[0][0]=0;
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++) {
if(i==n&&j==n) break;
auto coin = coins[i+j];
if(i<n)chmin(dp[i+1][j],dp[i][j]+dist(coin,{i+1,2}));
if(j<n)chmin(dp[i][j+1],dp[i][j]+dist(coin,{j+1,1}));
}
printf("%lld\n",dp[n][n]);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |