oj.uz

Submission #743488

# Submission time Handle Problem Language Result Execution time Memory
743488 2023-05-17T12:21:38 Z MohamedAhmed04 Akcija (COCI21_akcija) C++14
30 / 110
 818 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) ;
			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()) ;
			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) ;
			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 687 ms 412684 KB Output is correct
2 Correct 688 ms 438524 KB Output is correct
3 Correct 636 ms 384088 KB Output is correct
4 Correct 568 ms 379468 KB Output is correct
5 Correct 745 ms 433792 KB Output is correct
6 Correct 491 ms 300696 KB Output is correct
7 Correct 602 ms 343744 KB Output is correct
8 Correct 537 ms 308748 KB Output is correct
9 Correct 508 ms 300504 KB Output is correct
10 Correct 577 ms 355556 KB Output is correct
11 Correct 47 ms 95180 KB Output is correct
12 Correct 49 ms 95188 KB Output is correct
13 Correct 50 ms 95372 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 687 ms 412684 KB Output is correct
2 Correct 688 ms 438524 KB Output is correct
3 Correct 636 ms 384088 KB Output is correct
4 Correct 568 ms 379468 KB Output is correct
5 Correct 745 ms 433792 KB Output is correct
6 Correct 491 ms 300696 KB Output is correct
7 Correct 602 ms 343744 KB Output is correct
8 Correct 537 ms 308748 KB Output is correct
9 Correct 508 ms 300504 KB Output is correct
10 Correct 577 ms 355556 KB Output is correct
11 Correct 47 ms 95180 KB Output is correct
12 Correct 49 ms 95188 KB Output is correct
13 Correct 50 ms 95372 KB Output is correct
14 Correct 662 ms 412804 KB Output is correct
15 Correct 719 ms 438396 KB Output is correct
16 Correct 601 ms 384204 KB Output is correct
17 Correct 595 ms 379504 KB Output is correct
18 Correct 818 ms 433860 KB Output is correct
19 Correct 501 ms 300768 KB Output is correct
20 Correct 616 ms 343800 KB Output is correct
21 Correct 573 ms 308676 KB Output is correct
22 Correct 502 ms 300496 KB Output is correct
23 Correct 644 ms 355560 KB Output is correct
24 Correct 68 ms 95080 KB Output is correct
25 Correct 58 ms 95184 KB Output is correct
26 Correct 60 ms 95296 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 182 ms 111988 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 154640 KB Output is correct
2 Incorrect 263 ms 156628 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 687 ms 412684 KB Output is correct
2 Correct 688 ms 438524 KB Output is correct
3 Correct 636 ms 384088 KB Output is correct
4 Correct 568 ms 379468 KB Output is correct
5 Correct 745 ms 433792 KB Output is correct
6 Correct 491 ms 300696 KB Output is correct
7 Correct 602 ms 343744 KB Output is correct
8 Correct 537 ms 308748 KB Output is correct
9 Correct 508 ms 300504 KB Output is correct
10 Correct 577 ms 355556 KB Output is correct
11 Correct 47 ms 95180 KB Output is correct
12 Correct 49 ms 95188 KB Output is correct
13 Correct 50 ms 95372 KB Output is correct
14 Correct 662 ms 412804 KB Output is correct
15 Correct 719 ms 438396 KB Output is correct
16 Correct 601 ms 384204 KB Output is correct
17 Correct 595 ms 379504 KB Output is correct
18 Correct 818 ms 433860 KB Output is correct
19 Correct 501 ms 300768 KB Output is correct
20 Correct 616 ms 343800 KB Output is correct
21 Correct 573 ms 308676 KB Output is correct
22 Correct 502 ms 300496 KB Output is correct
23 Correct 644 ms 355560 KB Output is correct
24 Correct 68 ms 95080 KB Output is correct
25 Correct 58 ms 95184 KB Output is correct
26 Correct 60 ms 95296 KB Output is correct
27 Runtime error 793 ms 524288 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -