oj.uz

Submission #743477

# Submission time Handle Problem Language Result Execution time Memory
743477 2023-05-17T12:13:31 Z MohamedAhmed04 Akcija (COCI21_akcija) C++14
70 / 110
 709 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 = 2004 ;

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
		return (a[1] < b[1]) ;
}

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:62: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]
   62 |    while(dp[i][j].size() > k)
      |          ~~~~~~~~~~~~~~~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 591 ms 412504 KB Output is correct
2 Correct 638 ms 437924 KB Output is correct
3 Correct 554 ms 383592 KB Output is correct
4 Correct 540 ms 379084 KB Output is correct
5 Correct 669 ms 433520 KB Output is correct
6 Correct 473 ms 300184 KB Output is correct
7 Correct 519 ms 343296 KB Output is correct
8 Correct 476 ms 308216 KB Output is correct
9 Correct 465 ms 299852 KB Output is correct
10 Correct 561 ms 355056 KB Output is correct
11 Correct 51 ms 94596 KB Output is correct
12 Correct 47 ms 94624 KB Output is correct
13 Correct 49 ms 94760 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 591 ms 412504 KB Output is correct
2 Correct 638 ms 437924 KB Output is correct
3 Correct 554 ms 383592 KB Output is correct
4 Correct 540 ms 379084 KB Output is correct
5 Correct 669 ms 433520 KB Output is correct
6 Correct 473 ms 300184 KB Output is correct
7 Correct 519 ms 343296 KB Output is correct
8 Correct 476 ms 308216 KB Output is correct
9 Correct 465 ms 299852 KB Output is correct
10 Correct 561 ms 355056 KB Output is correct
11 Correct 51 ms 94596 KB Output is correct
12 Correct 47 ms 94624 KB Output is correct
13 Correct 49 ms 94760 KB Output is correct
14 Correct 686 ms 412272 KB Output is correct
15 Correct 665 ms 437888 KB Output is correct
16 Correct 561 ms 383656 KB Output is correct
17 Correct 602 ms 379012 KB Output is correct
18 Correct 709 ms 433484 KB Output is correct
19 Correct 456 ms 300264 KB Output is correct
20 Correct 573 ms 343360 KB Output is correct
21 Correct 445 ms 308300 KB Output is correct
22 Correct 483 ms 299976 KB Output is correct
23 Correct 513 ms 355032 KB Output is correct
24 Correct 47 ms 94624 KB Output is correct
25 Correct 48 ms 94608 KB Output is correct
26 Correct 48 ms 94752 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 642 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 113 ms 113636 KB Output is correct
2 Correct 117 ms 115632 KB Output is correct
3 Correct 92 ms 109472 KB Output is correct
4 Correct 93 ms 108224 KB Output is correct
5 Correct 135 ms 116920 KB Output is correct
6 Correct 55 ms 94720 KB Output is correct
7 Correct 124 ms 110792 KB Output is correct
8 Correct 64 ms 99884 KB Output is correct
9 Correct 67 ms 100420 KB Output is correct
10 Correct 47 ms 94796 KB Output is correct
11 Correct 57 ms 94528 KB Output is correct
12 Correct 52 ms 94516 KB Output is correct
13 Correct 108 ms 110860 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 155500 KB Output is correct
2 Correct 168 ms 157080 KB Output is correct
3 Correct 157 ms 146888 KB Output is correct
4 Correct 161 ms 145724 KB Output is correct
5 Correct 181 ms 159300 KB Output is correct
6 Correct 92 ms 112728 KB Output is correct
7 Correct 158 ms 140256 KB Output is correct
8 Correct 134 ms 125896 KB Output is correct
9 Correct 137 ms 128488 KB Output is correct
10 Correct 141 ms 127900 KB Output is correct
11 Correct 56 ms 94512 KB Output is correct
12 Correct 52 ms 94620 KB Output is correct
13 Correct 74 ms 107168 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 591 ms 412504 KB Output is correct
2 Correct 638 ms 437924 KB Output is correct
3 Correct 554 ms 383592 KB Output is correct
4 Correct 540 ms 379084 KB Output is correct
5 Correct 669 ms 433520 KB Output is correct
6 Correct 473 ms 300184 KB Output is correct
7 Correct 519 ms 343296 KB Output is correct
8 Correct 476 ms 308216 KB Output is correct
9 Correct 465 ms 299852 KB Output is correct
10 Correct 561 ms 355056 KB Output is correct
11 Correct 51 ms 94596 KB Output is correct
12 Correct 47 ms 94624 KB Output is correct
13 Correct 49 ms 94760 KB Output is correct
14 Correct 686 ms 412272 KB Output is correct
15 Correct 665 ms 437888 KB Output is correct
16 Correct 561 ms 383656 KB Output is correct
17 Correct 602 ms 379012 KB Output is correct
18 Correct 709 ms 433484 KB Output is correct
19 Correct 456 ms 300264 KB Output is correct
20 Correct 573 ms 343360 KB Output is correct
21 Correct 445 ms 308300 KB Output is correct
22 Correct 483 ms 299976 KB Output is correct
23 Correct 513 ms 355032 KB Output is correct
24 Correct 47 ms 94624 KB Output is correct
25 Correct 48 ms 94608 KB Output is correct
26 Correct 48 ms 94752 KB Output is correct
27 Runtime error 642 ms 524288 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -