Submission #743484

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
743484	2023-05-17T12:19:23 Z	MohamedAhmed04	Akcija (COCI21_akcija)	C++14	Compilation error	0 ms	0 KB

Main

#include <bits/stdc++.h>

using namespace std ;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()) ;

long long rand(long long l , long long r)
{
	return uniform_int_distribution<long long>(l , r)(rng) ;
}

const int MAX = 2010 ;

int arr[MAX] ;
int n , k ;

vector< pair<int , int> >vp ;
vector< array<long long , 3> >dp[MAX][MAX] ;

bool cmp(array<long long , 3>&a , array<long long , 3>&b)
{
	if(a[0] != b[0])
		return (a[0] > b[0]) ;
	else if(a[1] != b[1])
		return (a[1] < b[1]) ;
	else
		return (a[2] < b[2]) ;
}

long long val[MAX] ;

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>k ;
	for(int i = 1 ; i <= n ; ++i)
	{
		int w , d ;
		cin>>w>>d ;
		vp.emplace_back(d , w) ;
	}
	for(int i = 1 ; i <= n ; ++i)
		val[i] = rand(1 , 1e12) ;
	vp.emplace_back(0 , 0) ;
	sort(vp.begin() , vp.end()) ;
	for(int i = 0 ; i <= n ; ++i)
		dp[0][i].push_back({0 , 0 , 0}) ;
	for(int i = 1 ; i <= n ; ++i)
	{
		dp[i][0] = dp[i-1][0] ;
		for(int j = 1 ; j <= n ; ++j)
		{
			dp[i][j] = dp[i-1][j] ;
			for(auto &a : dp[i][j-1])
				dp[i][j].push_back(a) ;
			if(vp[j].first >= i)
			{
				for(auto &a : dp[i-1][j-1])
					dp[i][j].push_back({a[0]+1 , a[1] + vp[j].second , a[2] + val[j]}) ;
			}
			stable_sort(dp[i][j].begin() , dp[i][j].end() , cmp) ;
			dp[i][j].erase(unique(dp[i][j].begin() , dp[i][j].end()) , dp[i][j].end()) ;
			while(dp[i][j].size() > k)
				dp[i][j].pop_back() ;
		}
	}
	for(auto &a : dp[n][n])
		cout<<a[0]<<" "<<a[1]<<"\n" ;
	return 0 ;
}		

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:64:26: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   64 |    while(dp[i][j].size() > k)
      |          ~~~~~~~~~~~~~~~~^~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from Main.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Iter_comp_val<_Compare>::operator()(_Iterator, _Value&) [with _Iterator = __gnu_cxx::__normal_iterator<std::array<long long int, 3>*, std::vector<std::array<long long int, 3> > >; _Value = const std::array<long long int, 3>; _Compare = bool (*)(std::array<long long int, 3>&, std::array<long long int, 3>&)]':
/usr/include/c++/10/bits/stl_algobase.h:1324:14:   required from '_ForwardIterator std::__lower_bound(_ForwardIterator, _ForwardIterator, const _Tp&, _Compare) [with _ForwardIterator = __gnu_cxx::__normal_iterator<std::array<long long int, 3>*, std::vector<std::array<long long int, 3> > >; _Tp = std::array<long long int, 3>; _Compare = __gnu_cxx::__ops::_Iter_comp_val<bool (*)(std::array<long long int, 3>&, std::array<long long int, 3>&)>]'
/usr/include/c++/10/bits/stl_algo.h:2513:26:   required from 'void std::__merge_without_buffer(_BidirectionalIterator, _BidirectionalIterator, _BidirectionalIterator, _Distance, _Distance, _Compare) [with _BidirectionalIterator = __gnu_cxx::__normal_iterator<std::array<long long int, 3>*, std::vector<std::array<long long int, 3> > >; _Distance = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(std::array<long long int, 3>&, std::array<long long int, 3>&)>]'
/usr/include/c++/10/bits/stl_algo.h:2784:34:   required from 'void std::__inplace_stable_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::array<long long int, 3>*, std::vector<std::array<long long int, 3> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(std::array<long long int, 3>&, std::array<long long int, 3>&)>]'
/usr/include/c++/10/bits/stl_algo.h:5033:28:   required from 'void std::__stable_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::array<long long int, 3>*, std::vector<std::array<long long int, 3> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(std::array<long long int, 3>&, std::array<long long int, 3>&)>]'
/usr/include/c++/10/bits/stl_algo.h:5104:36:   required from 'void std::stable_sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<std::array<long long int, 3>*, std::vector<std::array<long long int, 3> > >; _Compare = bool (*)(std::array<long long int, 3>&, std::array<long long int, 3>&)]'
Main.cpp:62:55:   required from here
/usr/include/c++/10/bits/predefined_ops.h:194:23: error: binding reference of type 'std::array<long long int, 3>&' to 'const std::array<long long int, 3>' discards qualifiers
  194 |  { return bool(_M_comp(*__it, __val)); }
      |                ~~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/10/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Val_comp_iter<_Compare>::operator()(_Value&, _Iterator) [with _Value = const std::array<long long int, 3>; _Iterator = __gnu_cxx::__normal_iterator<std::array<long long int, 3>*, std::vector<std::array<long long int, 3> > >; _Compare = bool (*)(std::array<long long int, 3>&, std::array<long long int, 3>&)]':
/usr/include/c++/10/bits/stl_algo.h:2061:14:   required from '_ForwardIterator std::__upper_bound(_ForwardIterator, _ForwardIterator, const _Tp&, _Compare) [with _ForwardIterator = __gnu_cxx::__normal_iterator<std::array<long long int, 3>*, std::vector<std::array<long long int, 3> > >; _Tp = std::array<long long int, 3>; _Compare = __gnu_cxx::__ops::_Val_comp_iter<bool (*)(std::array<long long int, 3>&, std::array<long long int, 3>&)>]'
/usr/include/c++/10/bits/stl_algo.h:2522:26:   required from 'void std::__merge_without_buffer(_BidirectionalIterator, _BidirectionalIterator, _BidirectionalIterator, _Distance, _Distance, _Compare) [with _BidirectionalIterator = __gnu_cxx::__normal_iterator<std::array<long long int, 3>*, std::vector<std::array<long long int, 3> > >; _Distance = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(std::array<long long int, 3>&, std::array<long long int, 3>&)>]'
/usr/include/c++/10/bits/stl_algo.h:2784:34:   required from 'void std::__inplace_stable_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::array<long long int, 3>*, std::vector<std::array<long long int, 3> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(std::array<long long int, 3>&, std::array<long long int, 3>&)>]'
/usr/include/c++/10/bits/stl_algo.h:5033:28:   required from 'void std::__stable_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::array<long long int, 3>*, std::vector<std::array<long long int, 3> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(std::array<long long int, 3>&, std::array<long long int, 3>&)>]'
/usr/include/c++/10/bits/stl_algo.h:5104:36:   required from 'void std::stable_sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<std::array<long long int, 3>*, std::vector<std::array<long long int, 3> > >; _Compare = bool (*)(std::array<long long int, 3>&, std::array<long long int, 3>&)]'
Main.cpp:62:55:   required from here
/usr/include/c++/10/bits/predefined_ops.h:238:23: error: binding reference of type 'std::array<long long int, 3>&' to 'const std::array<long long int, 3>' discards qualifiers
  238 |  { return bool(_M_comp(__val, *__it)); }
      |                ~~~~~~~^~~~~~~~~~~~~~