Submission #496823

#TimeUsernameProblemLanguageResultExecution timeMemory
496823IerusCoin Collecting (JOI19_ho_t4)C++17
0 / 100
1 ms204 KiB
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize ("unroll-loops,Ofast,O3") #pragma GCC target("avx,avx2,fma") #define F first #define S second #define sz(x) (int)x.size() #define pb push_back #define eb emplace_back #define all(x) (x).begin(),(x).end() #define rall(x) (x).rbegin(),(x).rend() #define NFS ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ; #define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout) typedef long long ll; const int E = 1e6+777; const long long inf = 1e18+777; const int N = 1e5+777; const int MOD = 1e9+7; int n; pair<int,int> edge[N]; priority_queue<tuple<long long,int,int>> pq; int dist(int x1, int y1, int x2, int y2){ return abs(x1 - x2) + abs(y1 - y2); } bool used1[N], used2[N]; int main(){ cin >> n; for(int i = 1, x, y; i <= 2 * n; ++i){ cin >> x >> y; edge[i] = {x, y}; } for(int k = 1; k <= 2 * n; ++k){ int pos = 0; for(int i = 1; i <= n; ++i){ for(int j = 1; j <= 2; ++j){ ++pos; pq.push({-dist(edge[k].F,edge[k].S,i,j),k,pos}); } } } long long res = 0; while(!pq.empty()){ auto[d, pos, pos2] = pq.top(); pq.pop(); if(!used1[pos] && !used2[pos2]){ // cerr << "dist: " << d << " {"<< pos <<"} - " << "{"<<pos2<<"}\n"; res += -d; used1[pos] = true; used2[pos2] = true; } } cout << res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...