oj.uz

답안 #780761

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
780761 2023-07-12T12:47:02 Z Kryz Knapsack (NOI18_knapsack) C++17
73 / 100
 1000 ms 3976 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define sst string
#define pb push_back
#define maxco 100000+5
#define lld long double
#define cha ios_base::sync_with_stdio(false);
#define ffl cout.flush();
#define phi acos(-1)
#define mod 707
#define mr make_pair
#define pqin priority_queue<ll,vector<ll>,greater<>>
#define pqpair priority_queue<pair<ll,ll> ,vector<pair<ll,ll>>,greater<pair<ll,ll>>>
#define pqpair2 priority_queue<pair<pair<ll,ll>,pair<ll,ll>>,vector<pair<pi,pair<ll,ll>>>,greater<pair<pi,pair<ll,ll>>>>
#define INF 1000000009
#define MAXN 1000069
#define pi pair<ll,ll>
ll mvx[]={1,-1,0,0};
ll mvy[]={0,0,1,-1};


    float x,y;
        clock_t time_req;
void st(){

        time_req = clock();
}
void end(){
    time_req = clock() - time_req;
    cout << "Using pow function, it took " << (float)time_req/CLOCKS_PER_SEC << " seconds" << endl;
}


ll a[MAXN],b[MAXN],c[MAXN];
ll dp[MAXN];
int main(){
    cha
    ll n,x;
    cin>>x>>n;
    for(ll i=1;i<=n;i++){
        cin>>a[i]>>b[i]>>c[i];
    }
    for(ll i=x;i>=0;i--)dp[i]=-1e18;
    dp[0]=0;
    for(ll i=1;i<=n;i++){
        for(ll j=x;j>=0;j--){
            if(dp[j]!=-1e18){
                ll cnt=1;
                while(cnt<=c[i] && j+cnt*b[i]<=x){
                    dp[j+cnt*b[i]]=max(dp[j]+a[i]*cnt,dp[j+cnt*b[i]]);
                    cnt++;
                }
            }
        }
    }
    ll ans=0;
    for(ll i=x;i>=1;i--)ans=max(dp[i],ans);
    cout<<ans;
}


//ll n,m,k,a[MAXN];
//map<ll,ll> cnt;
//ll val[MAXN][69];
//ll dp[MAXN][69];
//ll bck[MAXN][69];
//int main(){
//    cin>>n>>m>>k;
//    for(ll i=1;i<=n;i++){
//        cin>>a[i];
//    }
//    for(ll i=0;i<=k;i++){
//        cnt.clear();
//        ll idx=1;
//        ll t=0;
//        for(ll j=1;j<=n;j++){
//            cnt[a[j]]++;
//            if(cnt[a[j]]>m)t++;
//            while(t>i){
//                if(cnt[a[idx]]>m)t--;
//                cnt[a[idx]]--;
//                idx++;
//            }
//            val[j][i]=idx-1;
//        }
//    }
////    for(ll j=0;j<=k;j++){
////        for(ll i=1;i<=n;i++){
////            cout<<j<<"   "<<i<<"  : "<<val[j][i]<<endl;
////        }
////    }
//    for(ll j=1;j<=n;j++){
//        for(ll i=0;i<=k;i++){
//            if(j<=i){
//                dp[j][i]=0;
//                continue;
//            }
//            else{
//                if(dp[val[j][i]][i-bck[j-1][i]]+1==dp[j-1][i]){
//                    //gabung
//                    dp[j][i]=dp[j-1][i];
//                    bck[j][i]=bck[j-1][i];
//                }
//                else if(dp[j-1][i-1]<dp[j-1][i]+1 && i>0){
//                    //dia bikin grup
//                    dp[j][i]=dp[j-1][i-1];
//                    bck[j][i]=bck[j-1][i-1]+1;
//                }
//                else{
//                    dp[j][i]=dp[j-1][i]+1;
//                    bck[j][i]=0;
//                }
//            }
//        }
//    }
////    for(ll i=0;i<=k;i++){
////        for(ll j=1;j<=n;j++){
////            cout<<i<<" "<<j<<"  : "<<dp[j][i]<<endl;
////        }
////    }
//    cout<<dp[n][k]<<endl;
//}

Subtask #1
12.0 / 12.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct

Subtask #4
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 122 ms 352 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 336 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 340 KB Output is correct

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 122 ms 352 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 336 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 17 ms 3668 KB Output is correct
36 Execution timed out 1077 ms 3976 KB Time limit exceeded
37 Halted 0 ms 0 KB -