Submission #127709

#	Time	Username	Problem	Language	Result	Execution time	Memory
127709		arnold518	Coin Collecting (JOI19_ho_t4)	C++14	37 / 100	20 ms	8312 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;

const int MAXN = 1000;
const ll INF = 1e17;

struct Point
{
    ll x, y;
    bool operator < (const Point& p) { return x<p.x; }
};

ll dist(Point p, Point q) { return abs(p.x-q.x)+abs(p.y-q.y); }

int N;
Point coin[2*MAXN+10];
ll dp[MAXN+10][MAXN+10];

int main()
{
    int i, j;

    scanf("%d", &N);
    for(i=1; i<=2*N; i++) scanf("%lld%lld", &coin[i].x, &coin[i].y);
    sort(coin+1, coin+2*N+1);

    for(i=0; i<=N; i++) for(j=0; j<=N; j++)
    {
        if(i==0 && j==0) continue;
        dp[i][j]=INF;
        if(i!=0) dp[i][j]=min(dp[i][j], dist(coin[i+j], {i, 1})+dp[i-1][j]);
        if(j!=0) dp[i][j]=min(dp[i][j], dist(coin[i+j], {j, 2})+dp[i][j-1]);
    }
    printf("%lld", dp[N][N]);
}

Compilation message (stderr)

joi2019_ho_t4.cpp: In function 'int main()':
joi2019_ho_t4.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
joi2019_ho_t4.cpp:28:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1; i<=2*N; i++) scanf("%lld%lld", &coin[i].x, &coin[i].y);
                           ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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