제출 #1284689

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1284689		zesanul_islam	Knapsack (NOI18_knapsack)	C++20	100 / 100	38 ms	3152 KiB

knapsack

//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <stack>
#include <queue>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <climits>
#define MOD 1000000007
#define Pie 3.1415926535897932384626433832795028841971
#define YES std::cout <<"YES" <<std::endl ;
#define NO std::cout <<"NO" <<std::endl ;
#define Choto_TO_Boro(x) std::sort ( x.begin() , x.end() ) ;
#define Boro_TO_Choto(x) std::sort ( x.begin() , x.end() ) ; std::reverse ( x.begin() , x.end() ) ;
#define OR ||
#define AND &&
#define ll long long
int main(){
    std::ios::sync_with_stdio ( false ) ; std::cin.tie ( 0 ) ; std::cout.tie ( 0 ) ; std::cout <<std::fixed <<std::setprecision ( 20 ) ;
    ll S , N , i = 0 ; std::cin >> S >> N ;
    std::vector < std::pair < ll , ll > > Weights[S+1] ;
    for ( i = 1 ; i <= N ; i++ ) {
        ll v , w , k ; std::cin >> v >> w >> k ;
        ll Max_Can_Take = S / w ;
        Weights[w].push_back ( { v , std::min ( k , Max_Can_Take ) } ) ;
    }
    for ( i = 1 ; i <= S ; i++ ) {
        Boro_TO_Choto(Weights[i]) ;
    }
    std::vector < std::pair < ll , ll > > All ;
    for ( i = 1 ; i <= S ; i++ ) {
        ll Take = S / i , j = 0 ;
        while ( j < Weights[i].size() AND Take ) {
            if ( Weights[i][j].second == 0 ) {
                j++ ; continue ;
            }
            All.push_back ( { Weights[i][j].first , i } ) ;
            Weights[i][j].second-- ; Take-- ;
        }
    }
    std::vector < ll > DP ( S+1 , -1 ) ; DP[0] = 0 ;
    for ( i = 0 ; i < All.size() ; i++ ) {
        for ( ll weight = S-All[i].second ; weight >= 0 ; weight-- ) {
            if ( DP[weight] != -1 ) DP[weight+All[i].second] = std::max ( DP[weight+All[i].second] , DP[weight] + All[i].first ) ;
        }
    }
    ll Max = 0 ;
    for ( i = 1 ; i <= S ; i++ ) Max = std::max ( Max , DP[i] ) ;
    std::cout <<Max <<std::endl ;
    return 0 ;
}

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 27 / 27