oj.uz

Submission #743482

# Submission time Handle Problem Language Result Execution time Memory
743482 2023-05-17T12:18:51 Z MohamedAhmed04 Akcija (COCI21_akcija) C++14
70 / 110
 703 ms 524288 KB 
#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]}) ;
			}
			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)
      |          ~~~~~~~~~~~~~~~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 592 ms 412732 KB Output is correct
2 Correct 671 ms 438428 KB Output is correct
3 Correct 549 ms 384332 KB Output is correct
4 Correct 554 ms 379604 KB Output is correct
5 Correct 636 ms 434192 KB Output is correct
6 Correct 452 ms 300748 KB Output is correct
7 Correct 566 ms 343772 KB Output is correct
8 Correct 464 ms 308812 KB Output is correct
9 Correct 453 ms 300448 KB Output is correct
10 Correct 538 ms 355480 KB Output is correct
11 Correct 51 ms 95096 KB Output is correct
12 Correct 48 ms 95184 KB Output is correct
13 Correct 48 ms 95304 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 592 ms 412732 KB Output is correct
2 Correct 671 ms 438428 KB Output is correct
3 Correct 549 ms 384332 KB Output is correct
4 Correct 554 ms 379604 KB Output is correct
5 Correct 636 ms 434192 KB Output is correct
6 Correct 452 ms 300748 KB Output is correct
7 Correct 566 ms 343772 KB Output is correct
8 Correct 464 ms 308812 KB Output is correct
9 Correct 453 ms 300448 KB Output is correct
10 Correct 538 ms 355480 KB Output is correct
11 Correct 51 ms 95096 KB Output is correct
12 Correct 48 ms 95184 KB Output is correct
13 Correct 48 ms 95304 KB Output is correct
14 Correct 616 ms 412772 KB Output is correct
15 Correct 679 ms 438336 KB Output is correct
16 Correct 596 ms 384232 KB Output is correct
17 Correct 574 ms 379536 KB Output is correct
18 Correct 655 ms 434008 KB Output is correct
19 Correct 437 ms 300748 KB Output is correct
20 Correct 548 ms 343788 KB Output is correct
21 Correct 490 ms 308788 KB Output is correct
22 Correct 449 ms 300492 KB Output is correct
23 Correct 573 ms 355548 KB Output is correct
24 Correct 57 ms 95164 KB Output is correct
25 Correct 61 ms 95176 KB Output is correct
26 Correct 56 ms 95392 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 703 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 114312 KB Output is correct
2 Correct 131 ms 116272 KB Output is correct
3 Correct 101 ms 109952 KB Output is correct
4 Correct 92 ms 108692 KB Output is correct
5 Correct 134 ms 117548 KB Output is correct
6 Correct 53 ms 95304 KB Output is correct
7 Correct 116 ms 111436 KB Output is correct
8 Correct 66 ms 100444 KB Output is correct
9 Correct 68 ms 100960 KB Output is correct
10 Correct 49 ms 95436 KB Output is correct
11 Correct 52 ms 95268 KB Output is correct
12 Correct 50 ms 95180 KB Output is correct
13 Correct 105 ms 111380 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 156004 KB Output is correct
2 Correct 189 ms 157680 KB Output is correct
3 Correct 163 ms 147496 KB Output is correct
4 Correct 156 ms 146244 KB Output is correct
5 Correct 181 ms 159852 KB Output is correct
6 Correct 98 ms 113112 KB Output is correct
7 Correct 174 ms 140852 KB Output is correct
8 Correct 134 ms 126624 KB Output is correct
9 Correct 138 ms 128992 KB Output is correct
10 Correct 121 ms 128488 KB Output is correct
11 Correct 51 ms 95180 KB Output is correct
12 Correct 50 ms 95112 KB Output is correct
13 Correct 75 ms 107696 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 592 ms 412732 KB Output is correct
2 Correct 671 ms 438428 KB Output is correct
3 Correct 549 ms 384332 KB Output is correct
4 Correct 554 ms 379604 KB Output is correct
5 Correct 636 ms 434192 KB Output is correct
6 Correct 452 ms 300748 KB Output is correct
7 Correct 566 ms 343772 KB Output is correct
8 Correct 464 ms 308812 KB Output is correct
9 Correct 453 ms 300448 KB Output is correct
10 Correct 538 ms 355480 KB Output is correct
11 Correct 51 ms 95096 KB Output is correct
12 Correct 48 ms 95184 KB Output is correct
13 Correct 48 ms 95304 KB Output is correct
14 Correct 616 ms 412772 KB Output is correct
15 Correct 679 ms 438336 KB Output is correct
16 Correct 596 ms 384232 KB Output is correct
17 Correct 574 ms 379536 KB Output is correct
18 Correct 655 ms 434008 KB Output is correct
19 Correct 437 ms 300748 KB Output is correct
20 Correct 548 ms 343788 KB Output is correct
21 Correct 490 ms 308788 KB Output is correct
22 Correct 449 ms 300492 KB Output is correct
23 Correct 573 ms 355548 KB Output is correct
24 Correct 57 ms 95164 KB Output is correct
25 Correct 61 ms 95176 KB Output is correct
26 Correct 56 ms 95392 KB Output is correct
27 Runtime error 703 ms 524288 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -