Submission #307620

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
307620	2020-09-28T20:31:06 Z	TeaTime	Semiexpress (JOI17_semiexpress)	C++17	Compilation error	0 ms	0 KB

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);
		}
	}
}

void solve() {
	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;
	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) {
			added++;
			dpt[i] = dpt[lastPos] + c * (i - lastPos);
			lastPos = i;
		}
		if (dpt[i] <= t) {
			add(curInd, added, s);
		}
		if (good[i]) {
			lastPos = i;
			curInd = !curInd;
			for (int j = 0; j <= k; j++) dpAns[j][curInd] = dpAns[j][!curInd];
			s = 0;
			added = 0;
		}


	}

	s = 0;
	for (int i = 0; i <= k; i++) s = max(s, dpAns[i][curInd]);
	cout << ans + s - 1;
}
int main()
{
	fastInp;

	cin >> n >> m >> k;
	solve();
	return 0;
	if (n <= 310) {
		solve();
		return 0;
	}
	cin >> a >> b >> c;
	ll t;
	cin >> t;
	vec.resize(m);

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

	
	ll ans = 0;
	set<ll> addt;
	for (int i = 0; i < vec.size(); i++) {
		ll lastInd = vec[i], lastIndT = (vec[i] - 1) * b;
		while (addt.size() != 0 && addt.size() > k) {
			addt.erase(--addt.end());
		}
		for (int j = 0; j < k; j++) {
			if (lastIndT > t) break;
			ll l = lastInd, r = n + 1;
			if (i < vec.size() - 1 && lastInd >= vec[i + 1]) break;
			while (r - l > 1) {
				ll mid = (l + r) / 2;
				if (lastIndT + (mid - lastInd) * a > t) {
					r = mid;
				}
				else {
					l = mid;
				}
			}

			if (l == lastInd) {
				if (j != 0) {
					addt.insert(-1);
				}
				else ans++;
				l++;
				lastIndT += (l - lastInd) * c;
				continue;
			}
			if (i < vec.size() - 1 && l >= vec[i + 1]) {
				if (j != 0) {
					addt.insert(-(vec[i + 1] - lastInd));
				}
				else ans += vec[i + 1] - lastInd;
				break;
			}
			
			l++;
			lastIndT += (l - lastInd) * c;
			if (j != 0) {
				addt.insert(-(l - lastInd));
			}
			else ans += l - lastInd;
			lastInd = l;
		}
	}
	k -= m;

	sort(addt.rbegin(), addt.rend());
	ll s = 0;
	for (int i = 0; i < min(ull(addt.size()), ull(k)); i++) {
		s += abs(*addt.begin());
		addt.erase(addt.begin());
	}

	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

1000000000 2 3000
1000000000 1 2
1000000000
1
1000000000
*/

Compilation message

semiexpress.cpp: In function 'int main()':
semiexpress.cpp:115:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |  for (int i = 0; i < vec.size(); i++) {
      |                  ~~^~~~~~~~~~~~
semiexpress.cpp:117:42: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
  117 |   while (addt.size() != 0 && addt.size() > k) {
      |                              ~~~~~~~~~~~~^~~
semiexpress.cpp:123:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |    if (i < vec.size() - 1 && lastInd >= vec[i + 1]) break;
      |        ~~^~~~~~~~~~~~~~~~
semiexpress.cpp:143:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |    if (i < vec.size() - 1 && l >= vec[i + 1]) {
      |        ~~^~~~~~~~~~~~~~~~
semiexpress.cpp:164:20: warning: comparison of integer expressions of different signedness: 'int' and 'const long long unsigned int' [-Wsign-compare]
  164 |  for (int i = 0; i < min(ull(addt.size()), ull(k)); i++) {
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/9/algorithm:62,
                 from semiexpress.cpp:4:
/usr/include/c++/9/bits/stl_algo.h: In instantiation of 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = std::reverse_iterator<std::_Rb_tree_const_iterator<long long int> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]':
/usr/include/c++/9/bits/stl_algo.h:4867:18:   required from 'void std::sort(_RAIter, _RAIter) [with _RAIter = std::reverse_iterator<std::_Rb_tree_const_iterator<long long int> >]'
semiexpress.cpp:162:33:   required from here
/usr/include/c++/9/bits/stl_algo.h:1968:22: error: no match for 'operator-' (operand types are 'std::reverse_iterator<std::_Rb_tree_const_iterator<long long int> >' and 'std::reverse_iterator<std::_Rb_tree_const_iterator<long long int> >')
 1968 |     std::__lg(__last - __first) * 2,
      |               ~~~~~~~^~~~~~~~~
In file included from /usr/include/c++/9/bits/stl_algobase.h:67,
                 from /usr/include/c++/9/bits/char_traits.h:39,
                 from /usr/include/c++/9/ios:40,
                 from /usr/include/c++/9/ostream:38,
                 from /usr/include/c++/9/iostream:39,
                 from semiexpress.cpp:1:
/usr/include/c++/9/bits/stl_iterator.h:276:7: note: candidate: 'constexpr std::reverse_iterator<_Iterator> std::reverse_iterator<_Iterator>::operator-(std::reverse_iterator<_Iterator>::difference_type) const [with _Iterator = std::_Rb_tree_const_iterator<long long int>; std::reverse_iterator<_Iterator>::difference_type = long int]'
  276 |       operator-(difference_type __n) const
      |       ^~~~~~~~
/usr/include/c++/9/bits/stl_iterator.h:276:33: note:   no known conversion for argument 1 from 'std::reverse_iterator<std::_Rb_tree_const_iterator<long long int> >' to 'std::reverse_iterator<std::_Rb_tree_const_iterator<long long int> >::difference_type' {aka 'long int'}
  276 |       operator-(difference_type __n) const
      |                 ~~~~~~~~~~~~~~~~^~~
/usr/include/c++/9/bits/stl_iterator.h:415:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr decltype ((__y.base() - __x.base())) std::operator-(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&)'
  415 |     operator-(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/9/bits/stl_iterator.h:415:5: note:   template argument deduction/substitution failed:
/usr/include/c++/9/bits/stl_iterator.h: In substitution of 'template<class _IteratorL, class _IteratorR> constexpr decltype ((__y.base() - __x.base())) std::operator-(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&) [with _IteratorL = std::_Rb_tree_const_iterator<long long int>; _IteratorR = std::_Rb_tree_const_iterator<long long int>]':
/usr/include/c++/9/bits/stl_algo.h:1968:22:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = std::reverse_iterator<std::_Rb_tree_const_iterator<long long int> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/9/bits/stl_algo.h:4867:18:   required from 'void std::sort(_RAIter, _RAIter) [with _RAIter = std::reverse_iterator<std::_Rb_tree_const_iterator<long long int> >]'
semiexpress.cpp:162:33:   required from here
/usr/include/c++/9/bits/stl_iterator.h:417:28: error: no match for 'operator-' (operand types are 'std::reverse_iterator<std::_Rb_tree_const_iterator<long long int> >::iterator_type' {aka 'std::_Rb_tree_const_iterator<long long int>'} and 'std::reverse_iterator<std::_Rb_tree_const_iterator<long long int> >::iterator_type' {aka 'std::_Rb_tree_const_iterator<long long int>'})
  417 |     -> decltype(__y.base() - __x.base())
/usr/include/c++/9/bits/stl_iterator.h:415:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr decltype ((__y.base() - __x.base())) std::operator-(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&)'
  415 |     operator-(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/9/bits/stl_iterator.h:415:5: note:   template argument deduction/substitution failed:
/usr/include/c++/9/bits/stl_iterator.h:417:28: note:   'std::reverse_iterator<std::_Rb_tree_const_iterator<long long int> >::iterator_type' {aka 'std::_Rb_tree_const_iterator<long long int>'} is not derived from 'const std::reverse_iterator<_Iterator>'
  417 |     -> decltype(__y.base() - __x.base())
/usr/include/c++/9/bits/stl_iterator.h:1212:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr decltype ((__x.base() - __y.base())) std::operator-(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&)'
 1212 |     operator-(const move_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/9/bits/stl_iterator.h:1212:5: note:   template argument deduction/substitution failed:
/usr/include/c++/9/bits/stl_iterator.h:417:28: note:   'std::reverse_iterator<std::_Rb_tree_const_iterator<long long int> >::iterator_type' {aka 'std::_Rb_tree_const_iterator<long long int>'} is not derived from 'const std::move_iterator<_IteratorL>'
  417 |     -> decltype(__y.base() - __x.base())
In file included from /usr/include/c++/9/vector:68,
                 from semiexpress.cpp:2:
/usr/include/c++/9/bits/stl_bvector.h:214:3: note: candidate: 'std::ptrdiff_t std::operator-(const std::_Bit_iterator_base&, const std::_Bit_iterator_base&)'
  214 |   operator-(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y)
      |   ^~~~~~~~
/usr/include/c++/9/bits/stl_bvector.h:214:39: note:   no known conversion for argument 1 from 'std::reverse_iterator<std::_Rb_tree_const_iterator<long long int> >::iterator_type' {aka 'std::_Rb_tree_const_iterator<long long int>'} to 'const std::_Bit_iterator_base&'
  214 |   operator-(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y)
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
In file included from /usr/include/c++/9/deque:67,
                 from /usr/include/c++/9/queue:60,
                 from semiexpress.cpp:7:
/usr/include/c++/9/bits/stl_deque.h:370:5: note: candidate: 'template<class _Tp, class _Ref, class _Ptr> typename std::_Deque_iterator<_Tp, _Ref, _Ptr>::difference_type std::operator-(const std::_Deque_iterator<_Tp, _Ref, _Ptr>&, const std::_Deque_iterator<_Tp, _Ref, _Ptr>&)'
  370 |     operator-(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
      |     ^~~~~~~~
/usr/include/c++/9/bits/stl_deque.h:370:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/9/bits/stl_algobase.h:67,
                 from /usr/include/c++/9/bits/char_traits.h:39,
                 from /usr/include/c++/9/ios:40,
                 from /usr/include/c++/9/ostream:38,
                 from /usr/include/c++/9/iostream:39,
                 from semiexpress.cpp:1:
/usr/include/c++/9/bits/stl_iterator.h:417:28: note:   'std::reverse_iterator<std::_Rb_tree_const_iterator<long long int> >::iterator_type' {aka 'std::_Rb_tree_const_iterator<long long int>'} is not derived from 'const std::_Deque_iterator<_Tp, _Ref, _Ptr>'
  417 |     -> decltype(__y.base() - __x.base())
In file included from /usr/include/c++/9/deque:67,
                 from /usr/include/c++/9/queue:60,
                 from semiexpress.cpp:7:
/usr/include/c++/9/bits/stl_deque.h:382:5: note: candidate: 'template<class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR> typename std::_Deque_iterator<_Tp, _Ref, _Ptr>::difference_type std::operator-(const std::_Deque_iterator<_Tp, _Ref, _Ptr>&, const std::_Deque_iterator<_Tp, _RefR, _PtrR>&)'
  382 |     operator-(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
      |     ^~~~~~~~
/usr/include/c++/9/bits/stl_deque.h:382:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/9/bits/stl_algobase.h:67,
                 from /usr/include/c++/9/bits/char_traits.h:39,
                 from /usr/include/c++/9/ios:40,
                 from /usr/include/c++/9/ostream:38,
                 from /usr/include/c++/9/iostream:39,
                 from semiexpress.cpp:1:
/usr/include/c++/9/bits/stl_iterator.h:417:28: note:   'std::reverse_iterator<std::_Rb_tree_const_iterator<long long int> >::iterator_type' {aka 'std::_Rb_tree_const_iterator<long long int>'} is not derived from 'const std::_Deque_iterator<_Tp, _Ref, _Ptr>'
  417 |     -> decltype(__y.base() - __x.base())
/usr/include/c++/9/bits/stl_algo.h: In instantiation of 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = std::reverse_iterator<std::_Rb_tree_const_iterator<long long int> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]':
/usr/include/c++/9/bits/stl_algo.h:4867:18:   required from 'void std::sort(_RAIter, _RAIter) [with _RAIter = std::reverse_iterator<std::_Rb_tree_const_iterator<long long int> >]'
semiexpress.cpp:162:33:   required from here
/usr/include/c++/9/bits/stl_iterator.h:1212:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr decltype ((__x.base() - __y.base())) std::operator-(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&)'
 1212 |     operator-(const move_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/9/bits/stl_iterator.h:1212:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/9/algorithm:62,
                 from semiexpress.cpp:4:
/usr/include/c++/9/bits/stl_algo.h:1968:22: note:   'std::reverse_iterator<std::_Rb_tree_const_iterator<long long int> >' is not derived from 'const std::move_iterator<_IteratorL>'
 1968 |     std::__lg(__last - __first) * 2,
      |               ~~~~~~~^~~~~~~~~
In file included from /usr/include/c++/9/vector:68,
                 from semiexpress.cpp:2:
/usr/include/c++/9/bits/stl_bvector.h:214:3: note: candidate: 'std::ptrdiff_t std::operator-(const std::_Bit_iterator_base&, const std::_Bit_iterator_base&)'
  214 |   operator-(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y)
      |   ^~~~~~~~
/usr/include/c++/9/bits/stl_bvector.h:214:39: note:   no known conversion for argument 1 from 'std::reverse_iterator<std::_Rb_tree_const_iterator<long long int> >' to 'const std::_Bit_iterator_base&'
  214 |   operator-(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y)
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
In file included from /usr/include/c++/9/deque:67,
                 from /usr/include/c++/9/queue:60,
                 from semiexpress.cpp:7:
/usr/include/c++/9/bits/stl_deque.h:370:5: note: candidate: 'template<class _Tp, class _Ref, class _Ptr> typename std::_Deque_iterator<_Tp, _Ref, _Ptr>::difference_type std::operator-(const std::_Deque_iterator<_Tp, _Ref, _Ptr>&, const std::_Deque_iterator<_Tp, _Ref, _Ptr>&)'
  370 |     operator-(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
      |     ^~~~~~~~
/usr/include/c++/9/bits/stl_deque.h:370:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/9/algorithm:62,
                 from semiexpress.cpp:4:
/usr/include/c++/9/bits/stl_algo.h:1968:22: note:   'std::reverse_iterator<std::_Rb_tree_const_iterator<long long int> >' is not derived from 'const std::_Deque_iterator<_Tp, _Ref, _Ptr>'
 1968 |     std::__lg(__last - __first) * 2,
      |               ~~~~~~~^~~~~~~~~
In file included from /usr/include/c++/9/deque:67,
                 from /usr/include/c++/9/queue:60,
                 from semiexpress.cpp:7:
/usr/include/c++/9/bits/stl_deque.h:382:5: note: candidate: 'template<class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR> typename std::_Deque_iterator<_Tp, _Ref, _Ptr>::difference_type std::operator-(const std::_Deque_iterator<_Tp, _Ref, _Ptr>&, const std::_Deque_iterator<_Tp, _RefR, _PtrR>&)'
  382 |     operator-(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
      |     ^~~~~~~~
/usr/include/c++/9/bits/stl_deque.h:382:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/9/algorithm:62,
                 from semiexpress.cpp:4:
/usr/include/c++/9/bits/stl_algo.h:1968:22: note:   'std::reverse_iterator<std::_Rb_tree_const_iterator<long long int> >' is not derived from 'const std::_Deque_iterator<_Tp, _Ref, _Ptr>'
 1968 |     std::__lg(__last - __first) * 2,
      |               ~~~~~~~^~~~~~~~~