Submission #880011

#	Time	Username	Problem	Language	Result	Execution time	Memory
880011		Parsa_Fallahpour	Akcija (COCI21_akcija)	C++17	90 / 110	5025 ms	324172 KiB

Main

/*
    Sag Template by ParsaF(RBS Master)
*/
 
// Heaven
 
#include <bits/stdc++.h>
/*
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
*/
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("sse4")

using namespace std;
 
 
#define TOF_IO                                   ios_base::sync_with_stdio(false);cin.tie(0) , cout.tie(0);
#define File_IO(x,y)                             freopen(x, "r", stdin); freopen(y, "w", stdout);
 
#define SEP                                      ' '
#define endl                                     '\n'
 
#define F                                        first
#define S                                        second
#define ALL(x)                                   (x).begin(), (x).end()
#define sz(x)                                    (x).size()
#define PB                                       push_back
 
#define toLower(x)                               transform(ALL(x), x.begin(), ::tolower)
#define toUpper(x)                               transform(ALL(x), x.begin(), ::toupper)
 
#define EDGE(arr, x, y)                          arr[x].PB(y), arr[y].PB(x)
#define WEDGE(arr, x, y, z)                      arr[x].PB({y, z}), arr[y].PB({x, z})
 
#define debug(x)                                 cerr << #x << ": " << x << endl
#define kill(x)                                  cout << x << endl, exit(0);
 
#define BIPC(x)                                  __builtin_popcount(x);
 
#define fD1(arr, ind, x)                         for(int i=0; i<ind; i++) arr[i] = x;
#define fD2(arr, ind1, ind2, x)                  for(int i=0; i<ind1; i++) for(int j=0; j<ind2; j++) arr[i][j] = x;
 
#define lc                                       (id << 1)
#define rc                                       ((id << 1) | 1)
#define isLeaf                                   r - l == 1
 
typedef long long       ll; 
typedef long double     lld;
typedef pair<ll, ll>    pll;
typedef pair<int, int>  pii;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const ll N    = 2e3 + 20;
const ll MAXN = 1e5 + 5;
const ll MT   = 323 + 0;
const ll sq   = 320;
 
const ll M    = 1e9 + 7;
const ll IM   = 1e18 + 37;
 
const ll LOG  = 31;
 
const ll INF  = 1e18; 
const lld EPS = 0.00000001;
 
ll prime[] = {1000000009, 1000000007, 988244353, 1000696969, 696969569, 1223232323};
 
 
/***********************************************************       Dark side of Heaven        ************************************************************/
 
/***************************************************************************************************************************************************/
 
 
ll POW(ll a, ll b, ll md); 
ll LIS(vector<ll>& v);
ll MOD(ll a, ll b);
 
void YES(bool flag);
void Yes(bool flag);
 
inline ll mod_add(ll a, ll b);
inline ll mod_neg(ll a, ll b);
inline ll mod_mlt(ll a, ll b);
 
/*
ll factI[N + 1], Numi[N + 1], fact[N + 1];
void InverseofNumber(ll p); void InverseofFactorial(ll p); void factorial(ll p); ll nPr(ll N, ll R, ll p); ll nCr(ll N, ll R); void comb();
*/

ll n, k;

pll arr[N];

vector<pll> dp[N][N];

bool cmp1(pll a, pll b)
{
    return a.S < b.S;
}

bool cmp2(pll a, pll b)
{
    if(a.F < b.F) return 0;
    if(a.F > b.F) return 1;
    return a.S < b.S;
}


void solve()
{
    cin >> n >> k;
    
    for(int i=1; i<=n; i++) cin >> arr[i].F >> arr[i].S;
    sort(arr+1, arr+n+1, cmp1);
    
    for(int i=0; i<=n; i++) dp[n+1][i].PB({0, 0});
    
    for(int i=n; i>0; i--)
    {
        for(int j=0; j<=n; j++)
        {
            dp[i][j] = dp[i+1][j];
            
            if(j >= arr[i].S) continue;
            
            for(pll P: dp[i+1][j+1]) dp[i][j].PB({P.F + 1, P.S + arr[i].F});
            
            sort(ALL(dp[i][j]), cmp2);
            dp[i][j].resize(min(k, ll(sz(dp[i][j]))));
        }
        
        for(int j=0; j<=n; j++)
        {
            dp[i+1][j].clear();
            dp[i+1][j].shrink_to_fit();
        }
    }
    
    for(pll P: dp[1][0]) cout << P.F << SEP << P.S << endl;
}
 
 
 
int main()
{
    TOF_IO;
    
    ll nTest=1;
    //cin >> nTest;
    
    while(nTest--) solve();
	
    return 0;
}
 
/********************************************************       The line that separates heaven and hell        *******************************************************/
 
// HELL
/*
void InverseofNumber(ll p = M){Numi[0] = Numi[1] = 1; for (ll i = 2; i <= N; i++){Numi[i] = Numi[p % i] * (p - p / i) % p;}}
void InverseofFactorial(ll p = M){factI[0] = factI[1] = 1;for (ll i = 2; i <= N; i++){factI[i] = (Numi[i] * factI[i - 1]) % p;}}
void factorial(ll p = M){fact[0] = 1;for (ll i = 1; i <= N; i++){fact[i] = (fact[i - 1] * i) % p;}}
ll nPr(ll N, ll R, ll p = M){if (N - R < 0 || R < 0) {return 0;}int ans = ((fact[N]) % p * factI[N - R]) % p;return ans;}
ll nCr(ll N, ll R){if (N - R < 0 || R < 0) {return 0;}int ans = ((fact[N] * factI[R]) % M * factI[N - R]) % M;return ans;}
void comb(){ll p = M;InverseofNumber(p);InverseofFactorial(p);factorial(p);}
*/
 
ll POW(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? MOD(a * POW(MOD(a * a, md), b / 2, md), md) : MOD(POW(MOD(a * a, md), b / 2, md), md)));}
ll MOD(ll a, ll b){return (a%b + b) % b;}
 
ll LIS(vector<ll>& v){if (v.size() == 0) {return 0;} vector<ll> tail(v.size(), 0); ll length = 1; tail[0] = v[0]; for (int i = 1; i < v.size(); i++) {auto b = tail.begin(), e = tail.begin() + length; auto it = lower_bound(b, e, v[i]); if (it == tail.begin() + length){tail[length++] = v[i];}else{*it = v[i];}} return length;}
 
void YES(bool flag){cout << (flag? "YES\n" : "NO\n");}
void Yes(bool flag){cout << (flag? "Yes\n" : "No\n");}
 
inline ll mod_add(ll a, ll b){ ll res = a + b; return (res >= M? res - M : res); }
inline ll mod_neg(ll a, ll b){ ll res = (abs(a - b) < M? a - b : (a - b) % M); return (res < 0? res + M : res); }
inline ll mod_mlt(ll a, ll b){ return (a * b % M); }

Compilation message (stderr)

Main.cpp: In function 'll LIS(std::vector<long long int>&)':
Main.cpp:173:133: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 | ll LIS(vector<ll>& v){if (v.size() == 0) {return 0;} vector<ll> tail(v.size(), 0); ll length = 1; tail[0] = v[0]; for (int i = 1; i < v.size(); i++) {auto b = tail.begin(), e = tail.begin() + length; auto it = lower_bound(b, e, v[i]); if (it == tail.begin() + length){tail[length++] = v[i];}else{*it = v[i];}} return length;}
      |                                                                                                                                   ~~^~~~~~~~~~

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