제출 #1257894

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1257894		brover29	Akcija (COCI21_akcija)	C++17	0 / 110	1032 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];
ll n,k,a[N],d[N];
void upd(multiset<pair<ll,ll>,cmp> &a){

    while(a.size()>k){
        auto it=(--a.end());
        a.erase(it);
    }
}
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];
    }
    dp[0].insert({0,0});
    for(ll i=1;i<=n;i++){
        dp[i]=dp[i-1];
        for(auto [cnt,w]:dp[i-1]){
            if(cnt+1>d[i])continue;
            dp[i].insert({cnt+1,w+a[i]});
        }
       // upd(dp[i]);
    }

    for(auto [cnt,w]:dp[n]){
        cout<<cnt<<' '<<w<<'\n';
        k--;
        if(!k)break;
    }
}

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