oj.uz

Submission #743473

# Submission time Handle Problem Language Result Execution time Memory
743473 2023-05-17T12:12:32 Z MohamedAhmed04 Akcija (COCI21_akcija) C++14
40 / 110
 160 ms 65176 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 = 100 + 10 ;

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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1108 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1108 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1108 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 19540 KB Output is correct
2 Correct 91 ms 21588 KB Output is correct
3 Correct 51 ms 15356 KB Output is correct
4 Correct 48 ms 14020 KB Output is correct
5 Correct 86 ms 22912 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 68 ms 16724 KB Output is correct
8 Correct 17 ms 5904 KB Output is correct
9 Correct 23 ms 6416 KB Output is correct
10 Correct 1 ms 852 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 60 ms 16740 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 61436 KB Output is correct
2 Correct 148 ms 63060 KB Output is correct
3 Correct 121 ms 52832 KB Output is correct
4 Correct 120 ms 51688 KB Output is correct
5 Correct 160 ms 65176 KB Output is correct
6 Correct 62 ms 18616 KB Output is correct
7 Correct 135 ms 46172 KB Output is correct
8 Correct 92 ms 31832 KB Output is correct
9 Correct 92 ms 34516 KB Output is correct
10 Correct 78 ms 33868 KB Output is correct
11 Correct 1 ms 612 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 32 ms 13200 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1108 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -