fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define fi first
  4. #define se second
  5. struct nom{
  6. 	int s, p, w;
  7. };
  8. int main(){
  9. 	//freopen("infarray.inp", "r", stdin);
  10. 	//freopen("infarray.out", "w", stdout);
  11.     ios::sync_with_stdio(false);
  12.     cin.tie(nullptr);
  13.     int n, m; cin >> n >> m;
  14.     vector<pair<int,pair<int, int>>> a(m);
  15.  
  16.     for(int i = 0; i < m; i++){
  17.     	cin >> a[i].fi >> a[i].se.fi >> a[i].se.se;
  18.     }
  19.  
  20.     vector<int> dp(n + 1, 1e9);
  21.     dp[0] = 0;
  22.     for(int i = 0; i <= m; i++){
  23.     	for(int j = n; j > 0; j--){
  24.     		for(int k = 1; k <= min(a[i].fi, j); k++){
  25.     			dp[j] = min(dp[j], dp[j - k] + k * a[i].se.fi + a[i].se.se);
  26.     		}
  27.     	}
  28.     }
  29.     cout << dp[n];
  30.  
  31.     return 0;
  32. }
  33.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
20 4
5 5 6
10 4 12
15 6 9
20 7 0
stdout
copy 
118
https://ideone.com/AuqFfo
language:
C++14 (gcc 8.3)
created:
9 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!