oj.uz

답안 #682408

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
682408 2023-01-16T08:11:52 Z vjudge1 Road Construction (JOI21_road_construction) C++17
100 / 100
 4821 ms 21888 KB 
#include <bits/stdc++.h>

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")

using namespace std;

#define int long long
#define ll long long
#define vi vector<long long>
#define pb push_back
#define sz(s) (int)s.size()
#define all(v) v.begin(), v.end()
#define show(a) cerr << #a <<" -> "<< a <<"\n"
#define pp pair<int,int>
#define FF first
#define SS second
#define endl "\n"
#define ld long double

const int N = 1e6 + 2, N3 = 1e3 + 6, inf = 1e18 + 7, LOG = 20;
map<char, int> md{{'N', 0}, {'E', 1}, {'S', 2}, {'W', 3}};
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
string stepDir = "RDLU";

int n, k, x[N], y[N];
multiset <int> st;
vector <pp> v;

//bool check(int z) {
//    int cnt = 0;
//    for (int i = 1; i < sz(v); i++) {
//        for (int j = 0; j < i; j++) {
//            if (cnt >= k) return 1;
//            if (abs(v[i].FF - v[j].FF) > z) break;
//            if (abs(v[i].FF - v[j].FF) + abs(v[i].SS - v[j].SS) <= z) {
//                cnt++;
////                cout << abs(v[i].FF - v[j].FF) + abs(y[i] - y[j]) << " " << x[j] << " " << y[j] << " " << cnt << "\n";
//            }
//        }
////        cout << cnt << " ";
//    }
//    return cnt >= k;
//}

main () {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);

    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];

        v.pb({x[i], y[i]});
    }
    sort(all(v));
//    int l = 0, r = inf, best = -1;
//    while (l <= r) {
//        int mid = (l + r) / 2;
//        if (check(mid)) {
//            best = mid;
//            r = mid - 1;
//        }
//        else l = mid + 1;
//    }

    vi ans;
    int cnt = 0;
    for (int i = 1; i < sz(v); i++) {
        for (int j = max(0ll, i - 3000); j < i; j++) {
            if (sz(st) < k) {
                st.insert(abs(v[i].FF - v[j].FF) + abs(v[i].SS - v[j].SS));
            }
            else {
                if (*st.rbegin() > abs(v[i].FF - v[j].FF) + abs(v[i].SS - v[j].SS)) {
                    st.erase(st.find(*st.rbegin()));
                    st.insert(abs(v[i].FF - v[j].FF) + abs(v[i].SS - v[j].SS));
                }
            }
        }
    }

    for (auto to : st) {
        cout << to << "\n";
    }



	return 0;
}

Compilation message

road_construction.cpp:3: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    3 | #pragma comment(linker, "/stack:200000000")
      | 
road_construction.cpp:48:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   48 | main () {
      | ^~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:74:9: warning: unused variable 'cnt' [-Wunused-variable]
   74 |     int cnt = 0;
      |         ^~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 302 ms 14656 KB Output is correct
2 Correct 286 ms 14600 KB Output is correct
3 Correct 177 ms 14680 KB Output is correct
4 Correct 160 ms 14660 KB Output is correct
5 Correct 257 ms 13560 KB Output is correct
6 Correct 3 ms 468 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4062 ms 21048 KB Output is correct
2 Correct 4734 ms 21092 KB Output is correct
3 Correct 150 ms 14584 KB Output is correct
4 Correct 4473 ms 20800 KB Output is correct
5 Correct 3897 ms 21052 KB Output is correct
6 Correct 4640 ms 21056 KB Output is correct
7 Correct 3836 ms 20280 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3011 ms 8192 KB Output is correct
2 Correct 3029 ms 8256 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 3025 ms 8284 KB Output is correct
5 Correct 2817 ms 8224 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3011 ms 8192 KB Output is correct
2 Correct 3029 ms 8256 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 3025 ms 8284 KB Output is correct
5 Correct 2817 ms 8224 KB Output is correct
6 Correct 2899 ms 8240 KB Output is correct
7 Correct 2858 ms 8252 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 2810 ms 8248 KB Output is correct
11 Correct 3059 ms 8228 KB Output is correct
12 Correct 2837 ms 8180 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 302 ms 14656 KB Output is correct
2 Correct 286 ms 14600 KB Output is correct
3 Correct 177 ms 14680 KB Output is correct
4 Correct 160 ms 14660 KB Output is correct
5 Correct 257 ms 13560 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 2858 ms 17128 KB Output is correct
8 Correct 2699 ms 17188 KB Output is correct
9 Correct 177 ms 14756 KB Output is correct
10 Correct 3070 ms 16380 KB Output is correct
11 Correct 3249 ms 16364 KB Output is correct
12 Correct 1629 ms 17180 KB Output is correct
13 Correct 2051 ms 15596 KB Output is correct

Subtask #6
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 302 ms 14656 KB Output is correct
2 Correct 286 ms 14600 KB Output is correct
3 Correct 177 ms 14680 KB Output is correct
4 Correct 160 ms 14660 KB Output is correct
5 Correct 257 ms 13560 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 4062 ms 21048 KB Output is correct
8 Correct 4734 ms 21092 KB Output is correct
9 Correct 150 ms 14584 KB Output is correct
10 Correct 4473 ms 20800 KB Output is correct
11 Correct 3897 ms 21052 KB Output is correct
12 Correct 4640 ms 21056 KB Output is correct
13 Correct 3836 ms 20280 KB Output is correct
14 Correct 3011 ms 8192 KB Output is correct
15 Correct 3029 ms 8256 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 3025 ms 8284 KB Output is correct
18 Correct 2817 ms 8224 KB Output is correct
19 Correct 2899 ms 8240 KB Output is correct
20 Correct 2858 ms 8252 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 2810 ms 8248 KB Output is correct
24 Correct 3059 ms 8228 KB Output is correct
25 Correct 2837 ms 8180 KB Output is correct
26 Correct 2858 ms 17128 KB Output is correct
27 Correct 2699 ms 17188 KB Output is correct
28 Correct 177 ms 14756 KB Output is correct
29 Correct 3070 ms 16380 KB Output is correct
30 Correct 3249 ms 16364 KB Output is correct
31 Correct 1629 ms 17180 KB Output is correct
32 Correct 2051 ms 15596 KB Output is correct
33 Correct 4821 ms 21816 KB Output is correct
34 Correct 4539 ms 21888 KB Output is correct
35 Correct 4771 ms 21060 KB Output is correct
36 Correct 2951 ms 21564 KB Output is correct
37 Correct 2874 ms 21856 KB Output is correct
38 Correct 3330 ms 20312 KB Output is correct