제출 #1287820

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1287820		TrieTr	Semiexpress (JOI17_semiexpress)	C++20	100 / 100	2 ms	584 KiB

semiexpress

#include<bits/stdc++.h>
using namespace std;

void local() {
	#define taskname ""
	if(fopen(taskname".inp", "r")) {
		freopen(taskname".inp", "r", stdin);
		freopen(taskname".out", "w", stdout);
	}
}

#define ll long long
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

template <class X, class Y> bool mini(X& x, Y y) {return x > y ? x = y, true : false;}
template <class X, class Y> bool maxi(X& x, Y y) {return x < y ? x = y, true : false;}

const int N = 1e6 + 5;

int n, m, k;
int a, b, c;
ll t;
int s[N];

namespace sub2 {
    bool check() {
        return n <= 3e2;
    }
    vector<pair<int, int>> ve;

    int find_pos(int l, int r, ll val) {
        int lo = l, hi = r, res = -1;
        while(lo <= hi) {
            int mid = (lo + hi) >> 1;
            //cout << mid << ' ' << val + 1ll * (mid - l) * a << '\n';
            if(val + 1ll * (mid - l) * a <= t) lo = (res = mid) + 1;
            else hi = mid - 1;
        }
        return res;
    }
    void solve() {
        ll cur = 0;
        for(int i = 1; i <= m; i++) {
            if(cur > t) break;
            int j = s[i]; ll tmp = cur;
            while(j < s[i + 1] && tmp <= t) {
                int p = find_pos(j, s[i + 1] - 1, tmp);
                if(p == -1) break;
                ve.emplace_back(j == s[i], p - j + 1);
                tmp += 1ll * (p - j + 1) * c; j = p + 1;
            }
            cur += 1ll * (s[i + 1] - s[i]) * b;
        }
        sort(ve.begin(), ve.end(), greater<pair<int, int>>());
        int res = 0;
        for(auto[type, val] : ve) {
            type ^= 1;
            if(k - type >= m) res += val;
            k -= type;
        }
        cout << res - 1;
    }
}

namespace sub3 {

    typedef tuple<ll, int, int> tlii;

    int find_pos(int l, int r, ll val) {
        int lo = l, hi = r, res = -1;
        while(lo <= hi) {
            int mid = (lo + hi) >> 1;
            //cout << mid << ' ' << val + 1ll * (mid - l) * a << '\n';
            if(val + 1ll * (mid - l) * a <= t) lo = (res = mid) + 1;
            else hi = mid - 1;
        }
        return res;
    }
    vector<int> ve;
    void solve() {
        ll cur = 0;
        priority_queue<tlii, vector<tlii>, greater<tlii>> pq;
        int res = 0;
        for(int i = 1; i <= m; i++) {
            if(cur > t) break;
            int j = s[i]; ll tmp = cur;
            int p = find_pos(j, s[i + 1] - 1, tmp);
            res += p - j + 1;
            tmp += 1ll * (p - j + 1) * c; j = p + 1;
            pq.emplace(tmp, j, s[i + 1] - 1);
            cur += 1ll * (s[i + 1] - s[i]) * b;
        }
        k -= m;
        int cnt = k;
        while(!pq.empty() && cnt > 0) {
            auto[val, j, ub] = pq.top(); pq.pop();
            int p = find_pos(j, ub, val);
            if(p == -1) continue;
            ve.emplace_back(p - j + 1);
            val += 1ll * (p - j + 1) * c; j = p + 1;
            if(j <= ub) {
                cnt--;
                pq.emplace(val, j, ub);
            }
        }
        sort(ve.begin(), ve.end(), greater<int>());
        for(int i = 0; i < min(k, (int)ve.size()); i++) res += ve[i];
        cout << res - 1;
    }
}

int main() {
	fastio; local();
	cin >> n >> m >> k;
    cin >> a >> b >> c >> t;
    for(int i = 1; i <= m; i++) cin >> s[i];
    s[m + 1] = n + 1;
    sub3::solve();
}

컴파일 시 표준 에러 (stderr) 메시지

semiexpress.cpp: In function 'void local()':
semiexpress.cpp:7:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:8:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |                 freopen(taskname".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 18 / 18
• Subtask 2: 30 / 30
• Subtask 3: 52 / 52