Submission #902514

#	Time	Username	Problem	Language	Result	Execution time	Memory
902514		jay_jayjay	Coin Collecting (JOI19_ho_t4)	C++17	37 / 100	156 ms	274432 KiB

joi2019_ho_t4

// {{{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)

joi2019_ho_t4.cpp: In function 'int main()':
joi2019_ho_t4.cpp:28:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         int n;scanf("%d",&n);
      |               ~~~~~^~~~~~~~~
joi2019_ho_t4.cpp:31:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         for(auto&[x,y]:coins)scanf("%d%d",&x,&y);
      |                              ~~~~~^~~~~~~~~~~~~~

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