oj.uz

답안 #490654

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
490654 2021-11-28T12:13:30 Z CyberSleeper Knapsack (NOI18_knapsack) C++14
29 / 100
 1 ms 332 KB 
#include <bits/stdc++.h>
#define fastio      ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define debug(x)    cout << "Line " << __LINE__ << ", " << #x << " is " << x << endl
#define fi          first
#define se          second
#define mp          make_pair
#define pb          push_back
#define ll          long long
#define ld          long double
#define pii         pair<int, int>
#define pll         pair<ll, ll>
#define ar3         array<int, 3>
#define nl          '\n'
#define tb          '\t'
#define sp          ' '
using namespace std;

const int MX=100005, MOD=1e9+7, BLOCK=500, INF=2e9+7;
const ll INFF=1e18+7;
const ld ERR=1e-7, pi=3.14159265358979323846;

int S, N, V[MX], W[MX], K[MX], DP[2][2005], cnt[2005];

int main(){
    fastio;
    cin >> S >> N;
    for(int i=1; i<=N; i++){
        cin >> V[i] >> W[i] >> K[i];
    }
    for(int i=1; i<=S; i++)
        DP[0][i]=-INF;
    DP[0][0]=0;
    for(int i=1; i<=N; i++){
        int now=i%2, bef=now^1;
        for(int j=0; j<=S; j++){
            DP[now][j]=DP[bef][j];
            cnt[j]=0;
            if(j>=W[i]){
                if(DP[now][j]<DP[bef][j-W[i]]+V[i]){
                    DP[now][j]=DP[bef][j-W[i]]+V[i];
                    cnt[j]=1;
                }
                if(cnt[j-W[i]]<K[i]){
                    if(DP[now][j]<DP[now][j-W[i]]+V[i]){
                        DP[now][j]=DP[now][j-W[i]]+V[i];
                        cnt[j]=cnt[j-W[i]]+1;
                    }else if(DP[now][j]==DP[now][j-W[i]]+V[i])
                        cnt[j]=min(cnt[j], cnt[j-W[i]]+1);
                }
            }
        }
    }
    N%=2;
    for(int i=0; i<S; i++)
        DP[N][S]=max(DP[N][S], DP[N][i]);
    cout << DP[N][S] << nl;
}

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Incorrect 1 ms 332 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 0 ms 332 KB Output is correct
16 Incorrect 1 ms 332 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 0 ms 332 KB Output is correct
16 Incorrect 1 ms 332 KB Output isn't correct
17 Halted 0 ms 0 KB -