Submission #1131037

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131037		duckindog	Akcija (COCI21_akcija)	C++17	90 / 110	5091 ms	32140 KiB

Main

#include<bits/stdc++.h>

using namespace std;

const int N = 2000 + 10;
int n, k;

struct Product { 
  int w, d;
  friend istream& operator >> (istream& is, Product& rhs) { 
    return is >> rhs.w >> rhs.d;
  }
} p[N];
multiset<pair<int, long long>> s[N];

int32_t main(){
	cin.tie(0)->sync_with_stdio(0);

  cin >> n >> k;
  for (int i = 1; i <= n; ++i) cin >> p[i];
  
  sort(p + 1, p + n + 1, [&](const auto& a, const auto& b) { 
    return a.d < b.d;
  });

  s[0] = {{0, 0}};
  for (int i = 1; i <= n; ++i) { 
    const auto& [w, d] = p[i];

    for (int j = d; j >= 1; --j) { 
      for (const auto& [cnt, cost] : s[j - 1]) { 
        s[j].insert({cnt + 1, cost - w});
        if ((int)s[j].size() > k) s[j].erase(s[j].begin());
      }
    }
  }

  vector<pair<int, long long>> answer(1);
  for (int i = 1; i <= n; ++i)
    answer.insert(answer.end(), s[i].begin(), s[i].end());

  sort(answer.begin(), answer.end(), greater<>());
  for (int i = 0; i < k; ++i)
    cout << answer[i].first << " " << -answer[i].second << "\n";
}

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