QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#737311 | #7739. Knapsack | harlem | WA | 0ms | 3636kb | C++14 | 1.8kb | 2024-11-12 15:26:47 | 2024-11-12 15:26:47 |
Judging History
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'