Submission #990851

#	Time	Username	Problem	Language	Result	Execution time	Memory
990851		12345678	Road Construction (JOI21_road_construction)	C++17	5 / 100	60 ms	8276 KiB

road_construction

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e3+5;

ll n, k;
pair<ll, ll> p[nx];
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
priority_queue<ll, vector<ll>, greater<ll>> dp[nx];

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>k;
    for (int i=0; i<n; i++) cin>>p[i].first>>p[i].second;
    sort(p, p+n);
    //for (int i=0; i<n; i++) cout<<"points "<<p[i].first<<' '<<p[i].second<<'\n';
    for (int i=0; i<n; i++) for (int j=0; j<i; j++) dp[i].push(p[i].first-p[j].first+abs(p[i].second-p[j].second));
    for (int i=0; i<n; i++) if (!dp[i].empty()) pq.push({dp[i].top(), i}), dp[i].pop();
    for (int t=1; t<=k; t++)
    {
        auto [d,idx]=pq.top();
        pq.pop();
        cout<<d<<'\n';
        if (!dp[idx].empty()) pq.push({dp[idx].top(), idx}), dp[idx].pop();
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 20
• Subtask 5: 0 / 27
• Subtask 6: 0 / 35