Cod sursa(job #3290662)

Utilizator ana.veronica13Ana Veronica Draghici ana.veronica13 Data 31 martie 2025 15:26:21
Problema Energii Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <fstream>

using namespace std;

#define MAX_G 1001
#define MAX_E 10001

int e[MAX_G], c[MAX_G], dp[MAX_E][2];

int main(){
  ifstream cin( "energii.in" );
  ofstream cout( "energii.out" );
  int g, w, i, j, ans;
  cin >> g >> w;
  for( i = 1; i <= g; i++ ){
    cin >> e[i] >> c[i];
  }
  for( i = 1; i < MAX_E; i++ ){
      dp[i][0] = dp[i][1] = 2100000000;
  }
  ans = 2100000000;
  for( i = 1; i < MAX_E; i++ ){
    for( j = 1; j <= g; j++ ){
      if( i >= e[j] )
        dp[i][1] = min( dp[i][0], dp[i - e[j]][0] + c[j] );
      else
        dp[i][1] = dp[i][0];
      if( i >= w && dp[i][1] < ans ){
        ans = dp[i][1];
      }
      dp[i][0] = dp[i][1];
      dp[i][1] = 2100000000;
    }
  }
  if( ans == 2100000000 )
    cout << "-1";
  else
    cout << ans;
  return 0;
}