Submission #307589

#	Time	Username	Problem	Language	Result	Execution time	Memory
307589		TeaTime	Semiexpress (JOI17_semiexpress)	C++17	48 / 100	37 ms	32504 KiB

semiexpress

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <random>
#include <chrono>
#include <tuple>
#include <random>
#include <cmath>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

const ll SIZE = 1e6 * 2 + 10, INF = 1e9 * 1e9 + 10;

vector<ll> vec;

ll dpAns[10000][2], dpt[SIZE], good[SIZE];

ll n, m, k, a, b, c;

void add(int curInd, int us, int s) {
	for (int i = k; i >= 0; i--) {
		if (i - us >= 0) {
			dpAns[i][curInd] = max(dpAns[i][curInd], dpAns[i - us][curInd] + s);
		}
	}
}

int main()
{
	fastInp;

	cin >> n >> m >> k;
	cin >> a >> b >> c;
	ll t;
	cin >> t;
	vec.resize(m);

	for (auto &cur : vec) cin >> cur;

	good[1] = 1;
	ll lastI = -1, curInd = 0;
	for (int i = 1; i <= n; i++) {
		dpt[i] = dpt[i - 1] + a;
		if (vec[lastI + 1] == i) {
			good[i] = 1;
			if (i == 1) {
				dpt[i] = 0;
				lastI++;
				continue;
			}
			dpt[i] = min(dpt[i], min(dpt[vec[lastI]] + c * (i - vec[lastI]), dpt[vec[lastI]] + b * (i - vec[lastI])));
			lastI++;
		}
	}

	k -= m;
	ll ans = 0, added = 0, lastPos = 1, s = 0;
	vector<ll> addt;
	for (int i = 1; i <= n; i++) {
		if (dpt[i] <= t) {
			ans++;
		}
		else {
			s++;
		}
		dpt[i] = min(dpt[i], dpt[i - 1] + a);
		
		if (dpt[i] > t || good[i]) {
			if (dpt[i] > t) s--;
			addt.push_back(s);
			if (dpt[i] > t) s++;
		}
		if (dpt[i] > t) {
			added = 1;
			s = 1;
			dpt[i] = dpt[lastPos] + c * (i - lastPos);
			lastPos = i;
		}
		if (dpt[i] > t) {
			s = 0;
			continue;
		}
		
		if (good[i]) {
			lastPos = i;
			curInd = !curInd;
			for (int j = 0; j <= k; j++) dpAns[j][curInd] = dpAns[j][!curInd];
			s = 0;
			added = 0;
		}
	}

	sort(addt.rbegin(), addt.rend());
	for (int i = 0; i < min(ull(addt.size()), ull(k)); i++) {
		add(curInd, 1, addt[i]);
	}
	s = 0;
	for (int i = 0; i <= k; i++) s = max(s, dpAns[i][curInd]);
	cout << ans + s - 1;
	return 0;
}
/*
10 3 5
10 3 5
30
1
6
10

10 3 5
10 3 5
25
1
6
10

90 10 12
100000 1000 10000
10000
1
10
20
30
40
50
60
70
80
90

12 3 4
10 1 2
30
1
11
12

300 8 16
345678901 123456789 234567890
12345678901
1
10
77
82
137
210
297
300
*/

Compilation message (stderr)

semiexpress.cpp: In function 'int main()':
semiexpress.cpp:103:20: warning: comparison of integer expressions of different signedness: 'int' and 'const long long unsigned int' [-Wsign-compare]
  103 |  for (int i = 0; i < min(ull(addt.size()), ull(k)); i++) {
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:66:14: warning: variable 'added' set but not used [-Wunused-but-set-variable]
   66 |  ll ans = 0, added = 0, lastPos = 1, s = 0;
      |              ^~~~~

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