Submission #1257895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257895		brover29	Akcija (COCI21_akcija)	C++17	90 / 110	1042 ms	589824 KiB

Main

#include <bits/stdc++.h>
//qwerty47924692
using namespace std;
using ll = long long;
const ll N=2005;
#define f first
#define s second
const string br="617283";
struct cmp{
    bool operator()(const pair<ll,ll> &a,const pair<ll,ll> &b)const{
        if(a.f==b.f)return a.s<b.s;
        return a.f>b.f;
    }
};
multiset<pair<ll,ll>,cmp>dp[N][N];
ll n,k,a[N],d[N],p[N];
void upd(multiset<pair<ll,ll>,cmp> &a){

    while(a.size()>k){
        auto it=(--a.end());
        a.erase(it);
    }
}bool comp(ll a,ll b){
    return d[a]<d[b];
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin>>n>>k;
    for(ll i=1;i<=n;i++){
        cin>>a[i]>>d[i];
        p[i]=i;
    }
    sort(p+1,p+1+n,&comp);

    dp[0][0].insert({0,0});
    for(ll i=1;i<=n;i++){
        dp[i][0]=dp[i-1][0];
        for(ll j=1;j<=n;j++){
            dp[i][j]=dp[i-1][j];
            for(auto [cnt,w]:dp[i-1][j-1]){
                if(cnt+1>d[p[i]])continue;
                dp[i][j].insert({cnt+1,w+a[p[i]]});
            }
            upd(dp[i][j]);
        }
    }
    for(ll i=n;i>=0;i--){
        for(auto [cnt,w]:dp[n][i]){
            cout<<cnt<<' '<<w<<'\n';
            k--;
            if(!k)return 0;
        }
    }
}

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