oj.uz

Submission #992350

# Submission time Handle Problem Language Result Execution time Memory
992350 2024-06-04T09:55:01 Z Kalata_56 Road Construction (JOI21_road_construction) C++14
59 / 100
 10000 ms 8744 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(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    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:20: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]
   20 |             if(kol.size()>K){
      |                ~~~~~~~~~~^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 6984 KB Output is correct
2 Correct 280 ms 6984 KB Output is correct
3 Correct 256 ms 7004 KB Output is correct
4 Correct 265 ms 7144 KB Output is correct
5 Correct 263 ms 5936 KB Output is correct
6 Correct 14 ms 348 KB Output is correct

Subtask #2
0 / 6.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1433 ms 4352 KB Output is correct
2 Correct 1503 ms 4348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1463 ms 4128 KB Output is correct
5 Correct 1615 ms 4352 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1433 ms 4352 KB Output is correct
2 Correct 1503 ms 4348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1463 ms 4128 KB Output is correct
5 Correct 1615 ms 4352 KB Output is correct
6 Correct 2885 ms 4220 KB Output is correct
7 Correct 2790 ms 4348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2785 ms 4348 KB Output is correct
11 Correct 2613 ms 4352 KB Output is correct
12 Correct 2817 ms 4352 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 6984 KB Output is correct
2 Correct 280 ms 6984 KB Output is correct
3 Correct 256 ms 7004 KB Output is correct
4 Correct 265 ms 7144 KB Output is correct
5 Correct 263 ms 5936 KB Output is correct
6 Correct 14 ms 348 KB Output is correct
7 Correct 4695 ms 8516 KB Output is correct
8 Correct 4716 ms 8520 KB Output is correct
9 Correct 280 ms 7020 KB Output is correct
10 Correct 4771 ms 8008 KB Output is correct
11 Correct 4916 ms 7752 KB Output is correct
12 Correct 4847 ms 8744 KB Output is correct
13 Correct 5020 ms 7588 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 6984 KB Output is correct
2 Correct 280 ms 6984 KB Output is correct
3 Correct 256 ms 7004 KB Output is correct
4 Correct 265 ms 7144 KB Output is correct
5 Correct 263 ms 5936 KB Output is correct
6 Correct 14 ms 348 KB Output is correct
7 Execution timed out 10028 ms 6468 KB Time limit exceeded
8 Halted 0 ms 0 KB -