oj.uz

Submission #743480

# Submission time Handle Problem Language Result Execution time Memory
743480 2023-05-17T12:17:30 Z MohamedAhmed04 Akcija (COCI21_akcija) C++17
70 / 110
 683 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
		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 589 ms 412956 KB Output is correct
2 Correct 624 ms 438508 KB Output is correct
3 Correct 585 ms 384260 KB Output is correct
4 Correct 531 ms 379400 KB Output is correct
5 Correct 654 ms 433916 KB Output is correct
6 Correct 433 ms 300804 KB Output is correct
7 Correct 528 ms 343856 KB Output is correct
8 Correct 477 ms 308864 KB Output is correct
9 Correct 441 ms 300448 KB Output is correct
10 Correct 516 ms 355640 KB Output is correct
11 Correct 48 ms 95180 KB Output is correct
12 Correct 46 ms 95152 KB Output is correct
13 Correct 47 ms 95312 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 589 ms 412956 KB Output is correct
2 Correct 624 ms 438508 KB Output is correct
3 Correct 585 ms 384260 KB Output is correct
4 Correct 531 ms 379400 KB Output is correct
5 Correct 654 ms 433916 KB Output is correct
6 Correct 433 ms 300804 KB Output is correct
7 Correct 528 ms 343856 KB Output is correct
8 Correct 477 ms 308864 KB Output is correct
9 Correct 441 ms 300448 KB Output is correct
10 Correct 516 ms 355640 KB Output is correct
11 Correct 48 ms 95180 KB Output is correct
12 Correct 46 ms 95152 KB Output is correct
13 Correct 47 ms 95312 KB Output is correct
14 Correct 683 ms 412804 KB Output is correct
15 Correct 667 ms 438372 KB Output is correct
16 Correct 556 ms 384208 KB Output is correct
17 Correct 542 ms 379432 KB Output is correct
18 Correct 630 ms 434020 KB Output is correct
19 Correct 442 ms 300796 KB Output is correct
20 Correct 532 ms 343804 KB Output is correct
21 Correct 445 ms 308876 KB Output is correct
22 Correct 465 ms 300516 KB Output is correct
23 Correct 572 ms 355556 KB Output is correct
24 Correct 51 ms 95180 KB Output is correct
25 Correct 53 ms 95184 KB Output is correct
26 Correct 48 ms 95304 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 583 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 108 ms 114196 KB Output is correct
2 Correct 125 ms 116232 KB Output is correct
3 Correct 95 ms 110028 KB Output is correct
4 Correct 104 ms 108864 KB Output is correct
5 Correct 121 ms 117580 KB Output is correct
6 Correct 50 ms 95308 KB Output is correct
7 Correct 111 ms 111400 KB Output is correct
8 Correct 75 ms 100496 KB Output is correct
9 Correct 68 ms 101004 KB Output is correct
10 Correct 56 ms 95436 KB Output is correct
11 Correct 47 ms 95188 KB Output is correct
12 Correct 47 ms 95080 KB Output is correct
13 Correct 104 ms 111316 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 155980 KB Output is correct
2 Correct 172 ms 157704 KB Output is correct
3 Correct 145 ms 147428 KB Output is correct
4 Correct 147 ms 146360 KB Output is correct
5 Correct 200 ms 159872 KB Output is correct
6 Correct 94 ms 113124 KB Output is correct
7 Correct 161 ms 140768 KB Output is correct
8 Correct 123 ms 126416 KB Output is correct
9 Correct 129 ms 129016 KB Output is correct
10 Correct 113 ms 128600 KB Output is correct
11 Correct 48 ms 95092 KB Output is correct
12 Correct 47 ms 95180 KB Output is correct
13 Correct 74 ms 107768 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 589 ms 412956 KB Output is correct
2 Correct 624 ms 438508 KB Output is correct
3 Correct 585 ms 384260 KB Output is correct
4 Correct 531 ms 379400 KB Output is correct
5 Correct 654 ms 433916 KB Output is correct
6 Correct 433 ms 300804 KB Output is correct
7 Correct 528 ms 343856 KB Output is correct
8 Correct 477 ms 308864 KB Output is correct
9 Correct 441 ms 300448 KB Output is correct
10 Correct 516 ms 355640 KB Output is correct
11 Correct 48 ms 95180 KB Output is correct
12 Correct 46 ms 95152 KB Output is correct
13 Correct 47 ms 95312 KB Output is correct
14 Correct 683 ms 412804 KB Output is correct
15 Correct 667 ms 438372 KB Output is correct
16 Correct 556 ms 384208 KB Output is correct
17 Correct 542 ms 379432 KB Output is correct
18 Correct 630 ms 434020 KB Output is correct
19 Correct 442 ms 300796 KB Output is correct
20 Correct 532 ms 343804 KB Output is correct
21 Correct 445 ms 308876 KB Output is correct
22 Correct 465 ms 300516 KB Output is correct
23 Correct 572 ms 355556 KB Output is correct
24 Correct 51 ms 95180 KB Output is correct
25 Correct 53 ms 95184 KB Output is correct
26 Correct 48 ms 95304 KB Output is correct
27 Runtime error 583 ms 524288 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -