oj.uz

Submission #975165

# Submission time Handle Problem Language Result Execution time Memory
975165 2024-05-04T14:12:54 Z vjudge1 Knapsack (NOI18_knapsack) C++17
0 / 100
 103 ms 262144 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maks=2000;
const int maxitem=20000;
const int inf=2e9;
int s,n;
vector<pair<int,int> > weight[maks+5];
vector<pair<int,int> > item;
int dp[maxitem+5][maks+5];

int cek(int idx,int brt){
    if(brt<0)return -inf;
    if(idx==(long long)item.size())return 0;
    int &res=dp[idx][brt];
    if(res!=-1)return res;
    auto[w,v]=item[idx];
    return res=max(cek(idx+1,brt),cek(idx+1,brt-w)+v);
}

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>s>>n;
    for(int r=1;r<=n;r++){
        int v,w,k;
        cin>>v>>w>>k;
        weight[w].push_back({v,k});
    }
    for(int d=1;d<=maks;d++){
        sort(weight[d].begin(),weight[d].end());
        int ambil= maks/d +1;
        while(ambil!=0 && !weight[d].empty()){
            auto &[v, k] = weight[d].back();
            item.push_back({d, v});
            k--;
            ambil--;
            if (k == 0) weight[d].pop_back();
        }
    }
    memset(dp,-1,sizeof dp);
    cout<<cek(0,s);
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 103 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 73 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 73 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 103 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 103 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -