#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <chrono>
#include <string>
#include <numeric>
#include <cmath>
#include <iomanip>
#include <climits>
#include <bitset>
#define all(x) (x).begin(), (x).end()
#define vec(n) vll arr(n);
#define printarr(arr) for(auto i:arr){cout<<i<<" ";}cout<<endl;
#define printdict(dict) for(auto i:dict)cout<<i.first<<": "<<i.second<<endl;
#define printadj(adj) for(ll i=0;i<n;i++){if(!adj[i].empty()){cout<<i<<": ";printarr(adj[i])}}
#define read(arr); for(ll i=0;i<arr.size();i++) cin>>arr[i];
#define readundirected(m) for(ll i=0;i<m;i++){ll a,b; cin>>a>>b; a--;b--; adj[a].pb(b);adj[b].pb(a);}
#define readdirected(m) for(ll i=0;i<m;i++){ll a,b; cin>>a>>b; a--;b--; adj[a].pb(b);}
#define readfunc(n) for(ll i=0;i<n;i++){ll a;cin>>a;a--;func_adj[i]=a;}
#define grid(n,m) for (ll i=1;i<=n;i++){for (ll j=1;j<=m;j++) cin>>graph[i][j];}
#define vll vector<ll>
#define sll set<ll>
#define msll multiset<ll>
#define qll queue<ll>
#define pll pair<ll,ll>
#define str string
#define pb push_back
#define ll long long
#define ld long double
using namespace std;
const str alph="abcdefghijklmnopqrstuvwxyz";
const str capalph="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const ll inf=5e5+1;
const ll graph_size=1000;
const ll mod=1e9+7;
const ld pi=3.141592653589793238462643383279502884197;
const ll large=1e18;
const ll small=-1e18;
// Fast Input/Output
void fastio(){
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
}
// File Input/Output
str fileio(const string&filePath=__FILE__){
size_t lastSlash=filePath.find_last_of('/');
size_t lastDot=filePath.rfind('.');
return filePath.substr(lastSlash+1,lastDot-lastSlash-1);
}
// For Yes Or No Problems
str yes_or_no(bool test){
if (test){
return "YES";
}
return "NO";
}
ll s,n;
int main(){
// auto start_time=chrono::steady_clock::now();
fastio();
// str filename=fileio();
// ifstream cin(filename+".in");
// ofstream cout(filename+".out");
ll t=1;
// cin>>t;
while (t--){
cin>>s>>n;
vector<pair<ll,pll>> arr(n);
for (ll i=0;i<n;i++){
cin>>arr[i].first>>arr[i].second.first>>arr[i].second.second;
}
vector<vector<pll>> weights(s+1);
for (auto i:arr){
weights[i.second.first].pb({i.first,i.second.second});
}
for (ll i=0;i<=s;i++){
sort(all(weights[i]));
reverse(all(weights[i]));
}
for (ll i=0;i<=s;i++){
if (weights[i].empty()){
continue;
}
ll sum=0;
ll ind=weights[i].size();
for (ll j=0;j<weights[i].size();j++){
sum+=weights[i][j].second;
if (sum*i>=s){
ind=j;
weights[i][ind].second-=(ceil((sum*i-s)/i));
break;
}
}
for (ll j=weights[i].size()-1;j>ind;j--){
weights[i].pop_back();
}
}
vector<vll> weights1(s+1);
for (ll i=0;i<s;i++){
for (ll j=0;j<weights[i].size();j++){
for (ll k=0;k<weights[i][j].second;k++){
weights1[i].pb(weights[i][j].first);
}
}
}
vector<vll> dp(s+1,vll(s+1,-1));
for (ll i=0;i<=s;i++){
dp[0][i]=0;
}
for (ll i=1;i<=s;i++){
for (ll j=0;j<=s;j++){
dp[i][j]=dp[i-1][j];
ll sum=0;
for (ll k=0;k<weights1[i].size();k++){
sum+=weights1[i][k];
if (!((k+1)*i<=j)){
break;
}
if (dp[i-1][j-(k+1)*i]!=-1){
dp[i][j]=max(dp[i][j],dp[i-1][j-(k+1)*i]+sum);
}
}
}
}
ll ans=dp[s][s];
cout<<ans<<"\n";
}
// auto end_time=chrono::steady_clock::now();
// auto elapsed_time=chrono::duration_cast<chrono::milliseconds>(end_time-start_time);
// cout<<"Elapsed time: "<<elapsed_time.count()<<" milliseconds\n";
}
Compilation message
knapsack.cpp: In function 'int main()':
knapsack.cpp:91:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for (ll j=0;j<weights[i].size();j++){
| ~^~~~~~~~~~~~~~~~~~
knapsack.cpp:105:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for (ll j=0;j<weights[i].size();j++){
| ~^~~~~~~~~~~~~~~~~~
knapsack.cpp:119:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | for (ll k=0;k<weights1[i].size();k++){
| ~^~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
12380 KB |
Output is correct |
| 2 |
Correct |
6 ms |
12380 KB |
Output is correct |
| 3 |
Correct |
6 ms |
12500 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
12380 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
12380 KB |
Output is correct |
| 2 |
Correct |
6 ms |
12380 KB |
Output is correct |
| 3 |
Correct |
6 ms |
12500 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
12380 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
12380 KB |
Output is correct |
| 2 |
Correct |
6 ms |
12380 KB |
Output is correct |
| 3 |
Correct |
6 ms |
12500 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
12380 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
