Submission #902514

#TimeUsernameProblemLanguageResultExecution timeMemory
902514jay_jayjayCoin Collecting (JOI19_ho_t4)C++17
37 / 100
156 ms274432 KiB
// {{{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);
      |                              ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...