oj.uz

Submission #992348

# Submission time Handle Problem Language Result Execution time Memory
992348 2024-06-04T09:52:41 Z Kalata_56 Road Construction (JOI21_road_construction) C++14
59 / 100
 10000 ms 10688 KB 
#include<bits/stdc++.h>
using namespace std;
pair<long long,long long> kor[250001];
priority_queue<long long> kol;
vector<long long> rez;
int main(){
    long long N,K;
    cin>>N>>K;
    for(long long i=0;i<N;i++){
        cin>>kor[i].first>>kor[i].second;
    }
    sort(kor,kor+N);
    for(int k=1;k<N;k++){
        for(long long i=k;i<N;i++){
            long long raz=abs(kor[i].first-kor[i-k].first)+abs(kor[i].second-kor[i-k].second);
            kol.push(raz);
            if(kol.size()>K){
                kol.pop();
            }
        }
        if(k>=1000){
            break;
        }
    }
    while(!kol.empty()){
        rez.push_back(kol.top());
        kol.pop();
    }
    sort(rez.begin(),rez.end());
    for(long long i=0;i<K;i++){
        cout<<rez[i]<<endl;
    }
    return 0;
}

Compilation message

road_construction.cpp: In function 'int main()':
road_construction.cpp:17:26: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   17 |             if(kol.size()>K){
      |                ~~~~~~~~~~^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 6976 KB Output is correct
2 Correct 301 ms 7048 KB Output is correct
3 Correct 284 ms 7148 KB Output is correct
4 Correct 279 ms 7012 KB Output is correct
5 Correct 309 ms 5952 KB Output is correct
6 Correct 15 ms 348 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10050 ms 9396 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1613 ms 9400 KB Output is correct
2 Correct 1640 ms 9540 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1537 ms 7228 KB Output is correct
5 Correct 1596 ms 9648 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1613 ms 9400 KB Output is correct
2 Correct 1640 ms 9540 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1537 ms 7228 KB Output is correct
5 Correct 1596 ms 9648 KB Output is correct
6 Correct 3011 ms 9296 KB Output is correct
7 Correct 2984 ms 9396 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2934 ms 9396 KB Output is correct
11 Correct 2547 ms 7248 KB Output is correct
12 Correct 2796 ms 9556 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 6976 KB Output is correct
2 Correct 301 ms 7048 KB Output is correct
3 Correct 284 ms 7148 KB Output is correct
4 Correct 279 ms 7012 KB Output is correct
5 Correct 309 ms 5952 KB Output is correct
6 Correct 15 ms 348 KB Output is correct
7 Correct 4542 ms 8708 KB Output is correct
8 Correct 4602 ms 10688 KB Output is correct
9 Correct 280 ms 6984 KB Output is correct
10 Correct 4399 ms 10008 KB Output is correct
11 Correct 4455 ms 9788 KB Output is correct
12 Correct 4579 ms 10600 KB Output is correct
13 Correct 4774 ms 9688 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 6976 KB Output is correct
2 Correct 301 ms 7048 KB Output is correct
3 Correct 284 ms 7148 KB Output is correct
4 Correct 279 ms 7012 KB Output is correct
5 Correct 309 ms 5952 KB Output is correct
6 Correct 15 ms 348 KB Output is correct
7 Execution timed out 10050 ms 9396 KB Time limit exceeded
8 Halted 0 ms 0 KB -