QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#738497#7739. KnapsacksongszhWA 2ms24024kbC++145.0kb2024-11-12 19:13:102024-11-12 19:13:12

Judging History

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

  • [2024-11-12 19:13:12]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:24024kb
  • [2024-11-12 19:13:10]
  • 提交

answer

#include <bits/stdc++.h>#define int long long
#define ll long long
#define ull unsigned long long
#define db double
#define ld long double
#define rep(i,l,r) for (int i = (int)(l); i <= (int)(r); ++ i )
#define rep1(i,l,r) for (int i = (int)(l); i >= (int)(r); -- i )
#define il inline
#define fst first
#define snd second
#define ptc putchar
#define Yes ptc('Y'),ptc('e'),ptc('s'),puts("")
#define No ptc('N'),ptc('o'),puts("")
#define YES ptc('Y'),ptc('E'),ptc('S'),puts("")
#define NO ptc('N'),ptc('O'),puts("")
#define pb emplace_back
#define sz(x) (int)(x.size())
#define all(x) x.begin(),x.end()
#define get(x) ((x - 1) / len + 1)
#define debug() puts("------------")

using namespace std;
typedef pair<int,int> PII;
typedef pair<int,PII> PIII;
typedef pair<ll,ll> PLL;
namespace szhqwq {
    template<class T> il void read(T &x) {
        x = 0; T f = 1; char ch = getchar();
        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;
    }
    template<class T,class... Args> il void read(T &x,Args &...x_) { read(x); read(x_...); }
    template<class T> il void print(T x) {
        if (x < 0) ptc('-'), x = -x; 
        if (x > 9) print(x / 10); ptc(x % 10 + '0');
    }
    template<class T,class T_> il void write(T x,T_ ch) { print(x); ptc(ch); }
    template<class T,class T_> il void chmax(T &x,T_ y) { x = max(x,y); }
    template<class T,class T_> il void chmin(T &x,T_ y) { x = min(x,y); }
    template<class T,class T_,class T__> il T qmi(T a,T_ b,T__ p) {
        T res = 1; while (b) {
            if (b & 1) res = res * a % p;
            a = a * a % p; b >>= 1;
        } return res;
    }
    template<class T> il T gcd(T a,T b) { if (!b) return a; return gcd(b,a % b); }
    template<class T,class T_> il void exgcd(T a, T b, T_ &x, T_ &y) {
        if (b == 0) { x = 1; y = 0; return; }
        exgcd(b,a % b,y,x); y -= a / b * x; return ;
    }
    template<class T,class T_> il T getinv(T x,T_ p) { T inv,y; exgcd(x,(T)p,inv,y); inv = (inv + p) % p; return inv; }
} using namespace szhqwq;
const int N = 5010,inf = 1e9,mod = 998244353;
const ull base = 131,base_ = 233;
const ll inff = 1e18;
int n,m,k; PII a[5002];

il bool cmp(PII x,PII y) { return x.fst < y.fst; }

namespace acacac {
    ll f[N][10002];
    PII g[N][10002];
    bool vis[N];

    il void work() {
        rep(i,1,n)
            rep1(j,m,a[i].fst) {
                f[i][j] = f[i - 1][j]; g[i][j] = g[i - 1][j];
                if (f[i - 1][j - a[i].fst] + a[i].snd > f[i][j]) {
                    f[i][j] = f[i - 1][j - a[i].fst] + 1ll * a[i].snd;
                    g[i][j] = {i - 1,j - a[i].fst};
                }
            }
        ll ans = 0;
        rep(i,0,n) {
            int pos = m;
            rep(j,1,n) vis[j] = 1;
            rep1(j,i,1) if (pos >= a[j].fst && f[j][pos] == f[j - 1][pos - a[j].fst] + a[j].snd) vis[j] = 0,pos -= a[j].fst;
            vector<int> v;
            rep(x,1,n) if (vis[x]) v.pb(a[x].snd);
            sort(all(v),greater<int>());
            ll s = 0;
            rep(i,0,min(sz(v),k) - 1) s += 1ll * v[i];
            // cerr << i << " " << f[i][m] << " " << s << '\n';
            chmax(ans,f[i][m] + s);
        }
        write(ans,'\n');
        // cerr << (&edpos - &stpos) / 1024 / 1024 << " MB\n" << sizeof(g) + sizeof(f) << " !!!\n";
        return ;
    }
}

ll f[510][510][510];
il void sub() {
    rep(i,1,n) rep(p,0,k)
        rep1(j,m,!p ? a[i].fst : 0) {
            f[i][j][p] = f[i - 1][j][p];
            if (p) {
                if (j >= a[i].fst) {
                    if (f[i - 1][j - a[i].fst][p] + a[i].snd >= f[i - 1][j][p - 1] + a[i].snd) {
                        chmax(f[i][j][p],f[i - 1][j - a[i].fst][p] + a[i].snd);
                    } else {
                        // if (f[i - 1][j][p - 1] + a[i].snd > f[i][j][p]) cerr << i << " " << j << " " << p << " " << a[i].fst << " " << a[i].snd << '\n';
                        chmax(f[i][j][p],f[i - 1][j][p - 1] + a[i].snd);
                    }
                } else {
                    // if (f[i - 1][j][p - 1] + a[i].snd > f[i][j][p]) cerr << i << " " << j << " " << p << " " << a[i].fst << " " << a[i].snd << '\n';
                    chmax(f[i][j][p],f[i - 1][j][p - 1] + a[i].snd);
                }
            } else chmax(f[i][j][p],f[i - 1][j - a[i].fst][p] + 1ll * a[i].snd);
        }
    ll ret = 0;
    rep(i,0,k) chmax(ret,f[n][m][i]);
    write(ret,'\n');
    return ;
}

il void solve() {
    //------------code------------
    read(n,m,k);
    rep(i,1,n) read(a[i].fst,a[i].snd);
    sort(a + 1,a + n + 1);
    if (n <= 500 && m <= 500 && k <= 500) return sub(),void();
    return acacac :: work(),void();
}

il void init() {
    return ;
}

signed main() {
    // freopen("knapsack.in","r",stdin);
    // freopen("knapsack.out","w",stdout);
    // init();
    int _ = 1;
    // read(_);
    while (_ -- ) solve();
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 12044kb

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: 2ms
memory: 13784kb

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: 0ms
memory: 24024kb

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:

1577075983

result:

wrong answer 1st numbers differ - expected: '2009456281', found: '1577075983'