QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#737311#7739. KnapsackharlemWA 0ms3636kbC++141.8kb2024-11-12 15:26:472024-11-12 15:26:47

Judging History

你现在查看的是最新测评结果

  • [2024-11-12 15:26:47]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3636kb
  • [2024-11-12 15:26:47]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef double db;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
template <typename Type>
using vec=vector<Type>;
template <typename Type>
using grheap=priority_queue<Type>;
template <typename Type>
using lrheap=priority_queue<Type,vector<Type>,greater<Type> >;
#define fir first
#define sec second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define dprint(x) cout<<#x<<"="<<x<<"\n";

const int inf=0x3f3f3f3f;
const int mod=1e9+7/*998244353*/;

const int N=5e3+5,W=1e4+5;

int n,wa,k;
struct jew{
    int w,v;
    bool use;
}js[N];

ll f[N][W],g[N];
ll ans,tans;
int cnt;

bool cmp1(jew a,jew b){
    return a.v<b.v;
}
bool cmp2(jew a,jew b){
    return a.w>b.w;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>wa>>k;
    for(int i=1;i<=n;i++){
        cin>>js[i].v>>js[i].w;
    }
    sort(js+1,js+1+n,cmp2);
    for(int i=n;i>=1;i--){
        for(int j=wa;j>=js[i].v;j--){
            f[i][j]=max(f[i+1][j],f[i+1][j-js[i].v]+js[i].w);
            g[i]=max(g[i],f[i][j]);
        }
    }
    grheap<ll> pq;
    vec<ll> ppd;
    for(int i=1;i<=n;i++){
        pq.push(js[i].w);
        tans=0,cnt=0;
        while(!pq.empty()){
            if(cnt>=k)break;
            ppd.pub(pq.top());
            tans+=pq.top();
            pq.pop();
            cnt++;
        }
        ans=max(ans,tans+g[i+1]);
        while(!ppd.empty()){
            pq.push(ppd.back());
            ppd.pop_back();
        }
    }
    cout<<ans;
    return 0;
}
/*
5 13 2
5 16
5 28
7 44
8 15
8 41
*/

詳細信息

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3636kb

input:

4 10 1
9 10
10 1
3 5
5 20

output:

30

result:

wrong answer 1st numbers differ - expected: '35', found: '30'