oj.uz

답안 #693836

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
693836 2023-02-03T09:44:09 Z 79brue Autobahn (COI21_autobahn) C++17
0 / 100
 1 ms 468 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll n, k, x, len;
ll l[300002], t[300002], r[300002];
vector<ll> point = {-1'000'000'000, 1'000'000'000};
ll cnt[300002], sum[300002], w[300002], wsum[300002]; /// 사람 수, 벌금 사람 수
ll ans;

int main(){
    scanf("%lld %lld %lld", &n, &k, &x);

    point.clear();
    for(int i=0; i<=2000; i++) point.push_back(i);

    for(ll i=1; i<=n; i++){
        scanf("%lld %lld %lld", &l[i], &t[i], &r[i]);
        r[i]++;
        point.push_back(l[i]), point.push_back(r[i]);
        if(l[i] + t[i] < r[i]) point.push_back(l[i] + t[i]);
    }
    sort(point.begin(), point.end());
    point.erase(unique(point.begin(), point.end()), point.end());
    len = (ll)point.size();

    for(ll i=1; i<=n; i++){
        ll lp = lower_bound(point.begin(), point.end(), l[i]) - point.begin();
        ll mp = lower_bound(point.begin(), point.end(), min(r[i], l[i] + t[i])) - point.begin();
        ll rp = lower_bound(point.begin(), point.end(), r[i]) - point.begin();

        cnt[lp]++, cnt[rp]--;
        sum[mp]++, sum[rp]--;
    }
    for(ll i=0; i<len-1; i++){
        if(i) cnt[i] += cnt[i-1], sum[i] += sum[i-1];
        if(cnt[i] < k) sum[i] = 0;
        w[i] = sum[i] * (point[i+1] - point[i]);
        wsum[i] = (i ? wsum[i-1] : 0LL) + w[i];
    }

    ll pnt;
    for(ll i=1; i<len; i++){
        pnt = upper_bound(point.begin(), point.end(), point[i] + x - 1) - 1 - point.begin();
        ans = max(ans, wsum[pnt-1] - wsum[i-1] + (point[i] + x - point[pnt]) * sum[pnt]);
    }

    for(ll i=0; i<len-1; i++){
        pnt = upper_bound(point.begin(), point.end(), point[i+1] - x) - 1 - point.begin();
        if(pnt) ans = max(ans, wsum[i] - wsum[pnt] + (point[pnt+1] - (point[i+1] - x)) * sum[pnt]);
    }

    printf("%lld", ans);
}

Compilation message

autobahn.cpp: In function 'int main()':
autobahn.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     scanf("%lld %lld %lld", &n, &k, &x);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
autobahn.cpp:20:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         scanf("%lld %lld %lld", &l[i], &t[i], &r[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -