oj.uz

Submission #743487

# Submission time Handle Problem Language Result Execution time Memory
743487 2023-05-17T12:20:46 Z MohamedAhmed04 Akcija (COCI21_akcija) C++14
70 / 110
 749 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()) ;
			dp[i][j].erase(unique(dp[i][j].begin() , dp[i][j].end()) , dp[i][j].end()) ;
			sort(dp[i][j].begin() , dp[i][j].end() , cmp) ;
			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:63: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]
   63 |    while(dp[i][j].size() > k)
      |          ~~~~~~~~~~~~~~~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 700 ms 412920 KB Output is correct
2 Correct 733 ms 438516 KB Output is correct
3 Correct 628 ms 384300 KB Output is correct
4 Correct 617 ms 379544 KB Output is correct
5 Correct 749 ms 434188 KB Output is correct
6 Correct 476 ms 300744 KB Output is correct
7 Correct 577 ms 343932 KB Output is correct
8 Correct 498 ms 308716 KB Output is correct
9 Correct 481 ms 300524 KB Output is correct
10 Correct 579 ms 355596 KB Output is correct
11 Correct 48 ms 95180 KB Output is correct
12 Correct 48 ms 95192 KB Output is correct
13 Correct 53 ms 95312 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 700 ms 412920 KB Output is correct
2 Correct 733 ms 438516 KB Output is correct
3 Correct 628 ms 384300 KB Output is correct
4 Correct 617 ms 379544 KB Output is correct
5 Correct 749 ms 434188 KB Output is correct
6 Correct 476 ms 300744 KB Output is correct
7 Correct 577 ms 343932 KB Output is correct
8 Correct 498 ms 308716 KB Output is correct
9 Correct 481 ms 300524 KB Output is correct
10 Correct 579 ms 355596 KB Output is correct
11 Correct 48 ms 95180 KB Output is correct
12 Correct 48 ms 95192 KB Output is correct
13 Correct 53 ms 95312 KB Output is correct
14 Correct 682 ms 412796 KB Output is correct
15 Correct 725 ms 438568 KB Output is correct
16 Correct 635 ms 384228 KB Output is correct
17 Correct 632 ms 379656 KB Output is correct
18 Correct 722 ms 433916 KB Output is correct
19 Correct 470 ms 300856 KB Output is correct
20 Correct 551 ms 343916 KB Output is correct
21 Correct 491 ms 308812 KB Output is correct
22 Correct 465 ms 300452 KB Output is correct
23 Correct 560 ms 355576 KB Output is correct
24 Correct 47 ms 95176 KB Output is correct
25 Correct 50 ms 95088 KB Output is correct
26 Correct 49 ms 95316 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 709 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 151 ms 114216 KB Output is correct
2 Correct 160 ms 116228 KB Output is correct
3 Correct 127 ms 110012 KB Output is correct
4 Correct 119 ms 108720 KB Output is correct
5 Correct 176 ms 117440 KB Output is correct
6 Correct 53 ms 95308 KB Output is correct
7 Correct 137 ms 111372 KB Output is correct
8 Correct 73 ms 100464 KB Output is correct
9 Correct 75 ms 100972 KB Output is correct
10 Correct 49 ms 95440 KB Output is correct
11 Correct 47 ms 95116 KB Output is correct
12 Correct 49 ms 95188 KB Output is correct
13 Correct 136 ms 111356 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 155980 KB Output is correct
2 Correct 214 ms 157644 KB Output is correct
3 Correct 198 ms 147404 KB Output is correct
4 Correct 196 ms 146364 KB Output is correct
5 Correct 234 ms 160032 KB Output is correct
6 Correct 107 ms 113108 KB Output is correct
7 Correct 193 ms 140864 KB Output is correct
8 Correct 149 ms 126424 KB Output is correct
9 Correct 154 ms 129104 KB Output is correct
10 Correct 151 ms 128536 KB Output is correct
11 Correct 50 ms 95072 KB Output is correct
12 Correct 49 ms 95188 KB Output is correct
13 Correct 91 ms 107716 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 700 ms 412920 KB Output is correct
2 Correct 733 ms 438516 KB Output is correct
3 Correct 628 ms 384300 KB Output is correct
4 Correct 617 ms 379544 KB Output is correct
5 Correct 749 ms 434188 KB Output is correct
6 Correct 476 ms 300744 KB Output is correct
7 Correct 577 ms 343932 KB Output is correct
8 Correct 498 ms 308716 KB Output is correct
9 Correct 481 ms 300524 KB Output is correct
10 Correct 579 ms 355596 KB Output is correct
11 Correct 48 ms 95180 KB Output is correct
12 Correct 48 ms 95192 KB Output is correct
13 Correct 53 ms 95312 KB Output is correct
14 Correct 682 ms 412796 KB Output is correct
15 Correct 725 ms 438568 KB Output is correct
16 Correct 635 ms 384228 KB Output is correct
17 Correct 632 ms 379656 KB Output is correct
18 Correct 722 ms 433916 KB Output is correct
19 Correct 470 ms 300856 KB Output is correct
20 Correct 551 ms 343916 KB Output is correct
21 Correct 491 ms 308812 KB Output is correct
22 Correct 465 ms 300452 KB Output is correct
23 Correct 560 ms 355576 KB Output is correct
24 Correct 47 ms 95176 KB Output is correct
25 Correct 50 ms 95088 KB Output is correct
26 Correct 49 ms 95316 KB Output is correct
27 Runtime error 709 ms 524288 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -