제출 #1310611

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310611		quollcucumber`	Autobahn (COI21_autobahn)	C++20	0 / 100	1 ms	332 KiB

autobahn

// #pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
// #pragma GCC target("avx2")
#define int long long
using namespace std;

signed main(){
    int n, k, x;
    cin >> n >> k >> x;
    int crime[n];
    vector<pair<int, pair<int, int>>> v;
    for(int i = 0; i < n; i++) {
        int l, t, r;
        cin >> l >> t >> r;
        v.push_back({l, {i, 1}});
        v.push_back({r + 1, {i, -2}});
        v.push_back({r + 1, {i + k, 3}});
        crime[i] = max(0ll, (r - l + 1)  - t);
    }
    sort(v.begin(), v.end());
    int overlapping[n];
    memset(overlapping, 0, sizeof(overlapping));
    int dx[n];
    memset(dx, 0, sizeof(dx));
    int pos = 0;
    int maxval = 0;
    int numon = 0;
    for(int i = -1000 ; i <= 1000 ; i++) {
        while(pos != v.size()-1 && v[pos].first <= i + x - 1) {
            if(v[pos].second.second == 1) {
                dx[v[pos].second.first]++;
                numon++;
            }else if(v[pos].second.second == -2){
                dx[v[pos].second.first]-= 2;
            }else {
                numon --;
                dx[v[pos].second.second ] = 0;
            }
            pos++;
        }
        for(int j = 0; j < n; j++) {
            overlapping[j] += dx[j];
        }
        int total = 0;
        for(int j = 0; j < n; j++) {
            total += min(overlapping[j], crime[j]);
        }
        if(numon <= k) {
            maxval = max(maxval, total);
        }
    }
    cout<<maxval<<'\n';
    return 0;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 50