Submission #1255268

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255268		bonic	Knapsack (NOI18_knapsack)	C++20	12 / 100	1 ms	328 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define int long long

bool cmp(array<int, 3>&a, array<int, 3>&b) {
    if (a[0] * b[1] > a[1] * b[0]) {
        return true;
    }
    else if (a[0] * b[1] == a[1] * b[0]) {
        return a[0] <= b[0];
    }
    else return false;
}

signed main() {
    int s, n; cin >> s >> n; vector<array<int, 3>> A;
    for (int i = 0; i < n; i++) {
        int u, v, w; cin >> u >> v >> w;
        A.push_back({u, v, w});
    }
    sort(A.begin(), A.end(), cmp); int sum = 0;
    for (int i = 0; i < n; i++) {
        // cout << A[i][0] << " " << A[i][1] << " " << A[i][2] << "\n";
        int x = s / A[i][1];
        x = min(x, A[i][2]);
        sum += A[i][0] * x; s -= A[i][1] * x;
    }
    cout << sum;
}

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