제출 #1125421

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1125421		FaustasK	Knapsack (NOI18_knapsack)	C++20	100 / 100	127 ms	1840 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

bool rikiavimas(pair<int, int> a, pair<int, int> b)
{
    return a.first > b.first;
}

int main()
{
    int S, N;
    cin >> S >> N;
    vector<pair<int, int>> Duom[2001];
    
    for(int i = 0; i<N; i++)
    {
        int kaina, svoris, kiekis;
        cin >> kaina >> svoris >> kiekis;
        
        Duom[svoris].push_back({kaina, kiekis});
    }
    
    //cout << '!' << endl;
    
    vector<int> Pasirinkimai[2001];
    for(int i = 1; i<=2000; i++)
    {
        //cout << '!';
        if(Duom[i].size() > 0) sort(Duom[i].begin(), Duom[i].end(), rikiavimas);
        int riba = 2000/i+1; ///atkreipti demesi ateity
        int kur = 0;
        int kiek = 0;
        //cout << '?' << endl;;
        for(int j = 0; j<riba; j++)
        {
            //if(i == 3)cout << j << endl;
            if(kur > int(Duom[i].size())-1)
            {
                Pasirinkimai[i].push_back(-1);
                continue;
            }
            //cout << '.' << endl;
            if(kiek > Duom[i][kur].second-1)
            {
                kur++;
                kiek = 0;
            }
            if(kur > Duom[i].size()-1)
            {
                Pasirinkimai[i].push_back(-1);
                continue;
            }
            Pasirinkimai[i].push_back(Duom[i][kur].first);
            kiek++;
        }
        //cout << endl;
    }
    
    //ofstream cout ("isvestis.txt");
    
    /*for(int i = 0; i<=2000; i++)
    {
        for(int j = 0; j<Pasirinkimai[i].size(); j++)
        {
            cout << Pasirinkimai[i][j] << ' ';
        }
        cout << endl;
    }*/
    
    vector<int> tuscias(2001, -1);
    deque<vector<int>> dp;
    dp.push_back(tuscias);
    dp[0][0] = 0;
    
    for(int i = 1; i<=2000; i++)
    {
        dp.push_back(dp[0]);
        for(int j = 0; j<=2000; j++)
        {
            if(dp[0][j] == -1) continue;
            int suma = 0;
            int sk=0;
            for(int k = j+i; k<=2000; k+=i)
            {
                if(Pasirinkimai[i][sk] == -1) break;
                suma += Pasirinkimai[i][sk++];
                dp[1][k] = max(dp[1][k], dp[0][j] + suma);
            }
        }
        /*for(int j = 0; j<=S; j++)
        {
            cout << dp[1][j] << ' ';
        }
        cout << endl;*/
        dp.pop_front();
    }
    
    int ats = -1;
    for(int i = 0; i<=S; i++) ats = max(ats, dp[0][i]);
    cout << ats;
    return 0;
}
/*
10 5
4 1 3
3 1 8
9 2 17
7 5 7
15 6 5
*/

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