Submission #1307978

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307978		nanaseyuzuki	Semiexpress (JOI17_semiexpress)	C++20	18 / 100	2 ms	584 KiB

semiexpress

#include <bits/stdc++.h>
// Kazusa_Megumi
#define ll long long
#define int long long
#define fi first
#define se second
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
using namespace std;

const int mn = 5e5 + 5, mod = 1e9 + 7, inf = 2e9;

int n, m, k, a, b, c, s[mn], res = -1;
ll t;

void solve() {
    cin >> n >> m >> k >> a >> b >> c >> t;
    for(int i = 1; i <= m; i++) cin >> s[i];
    s[m + 1] = n + 1;
	
	priority_queue<int, vector<int>, greater<int>> pq;
	for(int i = 1; i <= m; i++){
		ll pre_cost = 1ll * (s[i] - 1) * b;
		if(t - pre_cost < 0) break;
		int left = (t - pre_cost) / a;
		res += min(left + 1, (s[i + 1] - s[i]));
		// cerr << i << ' ' << min(left + 1, 1ll * (s[i + 1] - s[i])) << '\n';
		int cur = s[i] + left, j = 1;
		while(j <= k - m && cur < s[i + 1] - 1){
			ll cur_cost = pre_cost + (cur + 1 - s[i]) * c;
			if(t - cur_cost < 0) break;
			int left1 = (t - cur_cost) / a;
			int new_place = min(cur + 1 + left1, 1ll * (s[i + 1] - 1));

			pq.push(new_place - cur);
			cur = new_place; 
			j ++;
		}
	}

	int left = k - m;
	while(pq.size() && left --){
		res += pq.top();
		pq.pop();
	}
	cout << res << '\n';
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    if (fopen("Kazuki.INP", "r")) {
        freopen("Kazuki.INP", "r", stdin);
        freopen("Kazuki.OUT", "w", stdout);
    }
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

Compilation message (stderr)

semiexpress.cpp:49:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   49 | main() {
      | ^~~~
semiexpress.cpp: In function 'int main()':
semiexpress.cpp:53:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         freopen("Kazuki.INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         freopen("Kazuki.OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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