QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#738492 | #7739. Knapsack | highkj | WA | 1ms | 6012kb | C++14 | 1.8kb | 2024-11-12 19:12:09 | 2024-11-12 19:12:10 |
Judging History
answer
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define rep(i,x,y) for(register int i=x;i<=y;i++)
#define rep1(i,x,y) for(register int i=x;i>=y;--i)
#define int long long
#define fire signed
#define il inline
template<class T> il void print(T x) {
if(x<0) printf("-"),x=-x;
if (x > 9) print(x / 10);
putchar(x % 10 + '0');
}
const int bufsize = 230005;
char buf[bufsize], *f1, *f2;
#define getchar() (f1 == f2 && (f2 = buf + fread(f1 = buf, 1, bufsize, stdin)) == buf? EOF: *f1++)
template<class T> il void in(T &x) {
x = 0; char ch = getchar();
int f = 1;
while (ch < '0' || ch > '9') {if(ch=='-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
x *= f;
}
int T=1;
const int N=5e3+10,M=1e4+10;
int f[N][M];
struct node{
int v,w;
friend bool operator<(const node&a,const node&b) {
return a.v<b.v;
}
}s[N];
int n,m,k;
int vis[N],dis[N];
priority_queue<int,vector<int>,greater<int>>q;
void solve() {
in(n),in(m),in(k);
rep(i,1,n) in(s[i].v),in(s[i].w);
sort(s+1,s+1+n);
rep(i,1,n) {
rep(j,0,m) {
if(j<s[i].v) f[i][j]=f[i-1][j];
else f[i][j]=max(f[i-1][j],f[i-1][j-s[i].v]+s[i].w);
}
}
int ss=0;
rep1(i,n,1) {
dis[i]=ss;
while(q.size()>=k&&q.top()<s[i].w) ss-=q.top(),q.pop();
q.push(s[i].w);
ss+=s[i].w;
}
int res=false;
rep(i,1,n) {
res=max(res,dis[i]+f[i][m]);
}
printf("%lld\n",res);
}
fire main() {
// freopen("knapsack.in","r",stdin);
// freopen("knapsack.out","w",stdout);
while(T--) {
solve();
}
return false;
}
/*
5 5 1
4 13627
3 17167
1 14354
2 8880
2 12354
*/
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5824kb
input:
4 10 1 9 10 10 1 3 5 5 20
output:
35
result:
ok 1 number(s): "35"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
5 13 2 5 16 5 28 7 44 8 15 8 41
output:
129
result:
ok 1 number(s): "129"
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 6012kb
input:
10 50 1 44 182173741 38 163268500 36 114173760 30 521894533 25 89514235 12 516184197 42 971377551 35 28242326 31 480227821 31 388523197
output:
2489684102
result:
wrong answer 1st numbers differ - expected: '2009456281', found: '2489684102'