제출 #1312049

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1312049		torontotokyo	Akcija (COCI21_akcija)	C++20	10 / 110	498 ms	94912 KiB

Main

#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include "vector"
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native" )
#include <bits/stdc++.h>
#define vodka void
#define ll long long
#define pf push_front
#define f first
#define s second
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define ld long double
#define NO cout << "NO" << endl
#define YES cout << "YES" << endl
#define endl "\n"
#define acc accumulate 
#define ull unsigned long long
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define raha_gay_lord ios_base::sync_with_stdio(0),cin.tie(0), cout.tie(0)
  
using namespace std;
  
ll rch = 0, sch = 0;
  
const ll MOD = 1e9 + 7;
const ll GIGAMOD = 998244353;
const ll MAXN = 1e5 + 10;
const ll LOG = 16;
const ll GIGA_LOG = 20;
const ld pi = acos(-1);
const ll Inf = 1e18 + 5;
const ll N = 2e5 + 5;
const ll LIM = 30 * 1e4;
const ll tree = N * 4;
  
ll binpow(ll x, ll p, ll mod){
  if (!p) return 1;
  if (p % 2) return (x % mod * binpow(x, p - 1, mod)) % mod;
  ll xx = binpow(x, p / 2, mod);
  return (xx % mod * xx % mod) % mod;
}
ll lcm(ll a, ll b) {
  return abs(a * b) / __gcd(a, b);
} 
ll get_sum(ll x){
  return (x * (x + 1) / 2);
}
struct Node {
  ll w, d;
};
pair<ll, ll> dir[4] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
bool checker(ll x, ll y, ll n, ll m){
  return (x >= 0 && x < n && y >= 0 && y < m);
}
bool cmp(Node& a, Node& b){
  if (a.d != b.d) return a.d < b.d;
  return a.w < b.w;
}
bool cmp2(Node& a, Node& b){
  if (a.w != b.w) return a.w > b.w;
  return a.d < b.d;
}
vodka solve(){
  ll n, k;
  cin >> n >> k;
  vector<Node> a(n);
  for (ll i = 0; i < n; ++i) cin >> a[i].w >> a[i].d;
  if (n <= 20){
    vector<Node> pr;
    map<vector<ll>, ll> used;
    for (ll mask = 0; mask < (1LL << n); ++mask){
      vector<Node> b;
      vector<ll> idx;
      for (ll i = 0; i < n; ++i){
        if (mask & (1LL << i)){
          idx.pb(i);
          b.pb({a[i].w, a[i].d});
        }
      }
      if (used[idx]) continue;
      ll sz = 0, cnt = 0, cnt2 = 0;
      for (ll i = 0; i < b.size(); ++i){
        cnt++;
        if (b[i].d >= cnt){
          sz++;
          cnt2 += b[i].w;
        }
      }
      used[idx] = 1;
      pr.pb({sz, cnt2});
    }
    sort(all(pr), &cmp2);
    ll cnt = 0;
    for (ll i = 0; i < k; ++i){
      cout << pr[i].w << " " << pr[i].d << endl;
    }
    return;
  }
  if (k == 1){
    sort(all(a), &cmp);
    ll sz = 0, cnt2 = 0, cnt = 0; 
    for (ll i = 0; i < n; ++i){
      if (a[i].d >= cnt + 1){
        cnt++;
        sz++;
        cnt2 += a[i].w;
      }
    }
    cout << sz << " " << cnt2 << endl;
  }
}
int main(){
  raha_gay_lord;
  ll ttttt = 1;   
  //cin >> ttttt;
  //ll cnt = 1;         
  while (ttttt--){
    //cout << "Case " << cnt << ": ";
    solve();
    //cnt++;
  }
  #ifndef ONLINE_JUDGE
  cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  #endif
  return 0;
}

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