Submission #529451

#	Time	Username	Problem	Language	Result	Execution time	Memory
529451		penguinhacker	Akcija (COCI21_akcija)	C++14	90 / 110	5074 ms	21044 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=2000;
int n, k;
ar<int, 2> a[mxN];
vector<vector<ll>> dp;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> k;
	for (int i=0; i<n; ++i)
		cin >> a[i][1] >> a[i][0];
	sort(a, a+n);
	dp.push_back({a[0][1]});
	for (int i=1; i<n; ++i) {
		// extend max elements
		int old_sz=dp.size();
		if (dp.size()<a[i][0]) {
			vector<ll> t=dp.back();
			for (ll& x : t)
				x+=a[i][1];
			dp.push_back(t);
		}
		for (int j=old_sz-1; j; --j) { // update dp[j] with possible better elements from dp[j-1]
			vector<ll> t;
			t.reserve(k);
			for (int x=0, y=0; t.size()<k&&(x<dp[j-1].size()||y<dp[j].size());) {
				if (y==dp[j].size()||(x<dp[j-1].size()&&dp[j-1][x]+a[i][1]<=dp[j][y]))
					t.push_back(dp[j-1][x++]+a[i][1]);
				else
					t.push_back(dp[j][y++]);
			}
			swap(dp[j], t);
		}
		// update only 1
		if (dp[0].size()==k&&a[i][1]<dp[0].back())
			dp[0].pop_back();
		dp[0].insert(lower_bound(dp[0].begin(), dp[0].end(), a[i][1]), a[i][1]);
	}
	for (int i=dp.size()-1, j=0; ~i&&k; --k) {
		cout << i+1 << " " << dp[i][j++] << "\n";
		if (j==dp[i].size())
			--i, j=0;
	}
	if (k)
		cout << "0 0";
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:23:16: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} and 'std::array<int, 2>::value_type' {aka 'int'} [-Wsign-compare]
   23 |   if (dp.size()<a[i][0]) {
Main.cpp:32:31: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   32 |    for (int x=0, y=0; t.size()<k&&(x<dp[j-1].size()||y<dp[j].size());) {
      |                       ~~~~~~~~^~
Main.cpp:32:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |    for (int x=0, y=0; t.size()<k&&(x<dp[j-1].size()||y<dp[j].size());) {
      |                                    ~^~~~~~~~~~~~~~~
Main.cpp:32:55: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |    for (int x=0, y=0; t.size()<k&&(x<dp[j-1].size()||y<dp[j].size());) {
      |                                                      ~^~~~~~~~~~~~~
Main.cpp:33:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     if (y==dp[j].size()||(x<dp[j-1].size()&&dp[j-1][x]+a[i][1]<=dp[j][y]))
      |         ~^~~~~~~~~~~~~~
Main.cpp:33:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     if (y==dp[j].size()||(x<dp[j-1].size()&&dp[j-1][x]+a[i][1]<=dp[j][y]))
      |                           ~^~~~~~~~~~~~~~~
Main.cpp:41:19: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   41 |   if (dp[0].size()==k&&a[i][1]<dp[0].back())
      |       ~~~~~~~~~~~~^~~
Main.cpp:47:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   if (j==dp[i].size())
      |       ~^~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 10 / 10
• Subtask 5: 30 / 30
• Subtask 6: 0 / 20