oj.uz

Submission #990851

# Submission time Handle Problem Language Result Execution time Memory
990851 2024-05-31T13:46:48 Z 12345678 Road Construction (JOI21_road_construction) C++17
5 / 100
 60 ms 8276 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 8276 KB Output is correct
2 Correct 60 ms 8176 KB Output is correct
3 Correct 50 ms 5968 KB Output is correct
4 Correct 52 ms 5972 KB Output is correct
5 Correct 60 ms 7248 KB Output is correct
6 Correct 7 ms 5720 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 8276 KB Output is correct
2 Correct 60 ms 8176 KB Output is correct
3 Correct 50 ms 5968 KB Output is correct
4 Correct 52 ms 5972 KB Output is correct
5 Correct 60 ms 7248 KB Output is correct
6 Correct 7 ms 5720 KB Output is correct
7 Runtime error 1 ms 600 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 8276 KB Output is correct
2 Correct 60 ms 8176 KB Output is correct
3 Correct 50 ms 5968 KB Output is correct
4 Correct 52 ms 5972 KB Output is correct
5 Correct 60 ms 7248 KB Output is correct
6 Correct 7 ms 5720 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -