oj.uz

Submission #893486

# Submission time Handle Problem Language Result Execution time Memory
893486 2023-12-27T05:47:02 Z vjudge1 Road Construction (JOI21_road_construction) C++17
11 / 100
 440 ms 21132 KB 
#include <bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
using namespace std;
signed main(){
    int n,k;
    cin>>n>>k;
    vector <int> x(n),y(n);
    for(int i=0;i<n;i++)cin>>x[i]>>y[i];
    if(n<=1000){
        vector <int> v;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                v.pb(abs(x[i]-x[j])+abs(y[i]-y[j]));
            }
        }
        sort(all(v));
        
        for(int i=0;i<k;i++){
            cout<<v[i]<<"\n";
        }
        return 0;
    }
    
    multiset <pair <int,int> > ms;
    sort(all(x));
    for(int i=0;i<n-1;i++){
        ms.insert({abs(x[i]-x[i+1]),i+1});
    }
    for(int i=0;i<k;i++){
        int ind=ms.begin()->second;
        int val=ms.begin()->first;
        cout<<val<<"\n";
        ms.erase(ms.begin());
        if(ind<n-1){
            ms.insert({val+x[ind+1]-x[ind],ind+1});
        }
    }
     
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 7056 KB Output is correct
2 Correct 55 ms 7096 KB Output is correct
3 Correct 35 ms 5140 KB Output is correct
4 Correct 35 ms 5056 KB Output is correct
5 Correct 50 ms 5812 KB Output is correct
6 Correct 17 ms 5580 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 440 ms 21132 KB Output is correct
2 Correct 405 ms 21080 KB Output is correct
3 Correct 35 ms 5068 KB Output is correct
4 Correct 224 ms 21012 KB Output is correct
5 Correct 207 ms 20996 KB Output is correct
6 Correct 208 ms 21072 KB Output is correct
7 Correct 245 ms 20308 KB Output is correct

Subtask #3
0 / 7.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 7056 KB Output is correct
2 Correct 55 ms 7096 KB Output is correct
3 Correct 35 ms 5140 KB Output is correct
4 Correct 35 ms 5056 KB Output is correct
5 Correct 50 ms 5812 KB Output is correct
6 Correct 17 ms 5580 KB Output is correct
7 Incorrect 181 ms 9576 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 7056 KB Output is correct
2 Correct 55 ms 7096 KB Output is correct
3 Correct 35 ms 5140 KB Output is correct
4 Correct 35 ms 5056 KB Output is correct
5 Correct 50 ms 5812 KB Output is correct
6 Correct 17 ms 5580 KB Output is correct
7 Correct 440 ms 21132 KB Output is correct
8 Correct 405 ms 21080 KB Output is correct
9 Correct 35 ms 5068 KB Output is correct
10 Correct 224 ms 21012 KB Output is correct
11 Correct 207 ms 20996 KB Output is correct
12 Correct 208 ms 21072 KB Output is correct
13 Correct 245 ms 20308 KB Output is correct
14 Incorrect 276 ms 19984 KB Output isn't correct
15 Halted 0 ms 0 KB -