Submission #530956

#TimeUsernameProblemLanguageResultExecution timeMemory
530956SlavitaAkcija (COCI21_akcija)C++14
90 / 110
1693 ms524292 KiB
#include <bits/stdc++.h> #pragma optimize("O3") #pragma GCC optimize("-O3") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("fast-math") //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> #define ve vector<int> #define pb push_back #define mp make_pair #define fi first #define se second #define pi pair<int,int> #define all(v) v.begin(),v.end() #define si(v) (int)v.size() #define en '\n' #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> #define ordered_muiltiset tree<int, null_type,less_equal<>, rb_tree_tag,tree_order_statistics_node_update> //#define int long long using namespace std; //using namespace __gnu_pbds; typedef long long ll; typedef unsigned long long ull; const int N = 2e3 + 228; const int big = 1e9 + 228; const ll llbig = 1e18 + 228; //ordered_set os; // os.order_of_key(4), (*os.find_by_order(5)) int n, m, ans, k; pair<ll, ll> a[N]; set<ll> dp[N][N]; bool cmp(pair<ll, ll> a, pair<ll, ll> b){ if (a.se <= b.se) return 1; return 0; } void upd(ll &a, ll b){ if (a > b) {a = b;} } //#undef int int main(){ //#define int long long iostream::sync_with_stdio(false); cin.tie(0); ios_base::sync_with_stdio(false); cout.tie(0); //freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); cin >> n >> k; for (int i = 1; i <= n; i++){ cin >> a[i].fi >> a[i].se; } stable_sort(a + 1, a + n + 1, cmp); dp[0][0].insert(0); for (int i = 0; i < n; i++){ for (int j = 0; j <= n; j++){ while(si(dp[i][j]) > k) dp[i][j].erase(--dp[i][j].end()); for (auto item : dp[i][j]){ dp[i + 1][j].insert(item); } if (j + 1 <= a[i + 1].se) { for (auto item : dp[i][j]){ dp[i + 1][j + 1].insert(item + a[i + 1].fi); } } } } set<pair<ll, ll>> ans; for (int j = 1; j <= n; j++) { for (auto item : dp[n][j]){ ans.insert({-j, item}); } } int kol = 0; for (auto item : ans){ kol++; if (kol > k) break; cout << -item.fi << ' ' << item.se << en; } if (kol <= k){ for (int i = kol + 1; i <= k; i++) cout << 0 << ' ' << 0 << en; } return 0; } /* */

Compilation message (stderr)

Main.cpp:2: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    2 | #pragma optimize("O3")
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...