Advertisement
Patrickmeme

Venus MLE

Jun 11th, 2023
638
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.25 KB | None | 0 0
  1. #include <fstream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <bitset>
  5. using namespace std;
  6.  
  7. ifstream cin("venus.in");
  8. ofstream cout("venus.out");
  9.  
  10. struct com{
  11.     int val,lim,ind;
  12. } v[1001];
  13.  
  14. bitset <1001> frv;
  15. bitset <1001> cr2[8785];
  16.  
  17. vector <int> rasp;
  18.  
  19. int dp[1001][8785];
  20. bool fost[1001][8785];
  21. string conv[]={"ianuarie","februarie","martie","aprilie","mai","iunie","iulie","august","septembrie","octombrie","noiembrie","decembrie"};
  22.  
  23. bool cmp(com a,com b){
  24.     if(a.lim<b.lim)
  25.         return 1;
  26.     return 0;
  27. }
  28.  
  29. int convF(string s){
  30.     int i,su;
  31.     i=su=0;
  32.     while(conv[i]!=s){
  33.         if(i%2==0)
  34.             su+=31;
  35.         else if(i%2==1 && i!=1)
  36.             su+=30;
  37.         else
  38.             su+=29;
  39.         i++;
  40.     }
  41.     return su;
  42. }
  43.  
  44. int main()
  45. {
  46.     string s;
  47.     int n,t,i,zi,h,max1,j,sum=0,ci;
  48.     cin>>n>>t;
  49.     for(i=1;i<=n;i++){
  50.         v[i].ind=i;
  51.         cin>>v[i].val>>zi>>s>>h;
  52.         sum+=v[i].val;
  53.         v[i].lim=(convF(s)+zi-1)*24+h;
  54.         ///printf("%d\n",v[i].lim);
  55.     }
  56.     sort(v+1 ,v+n+1,cmp);
  57.     fost[0][0]=1;
  58.     for(i=1;i<=n;i++){
  59.         //printf("|%d %d|",v[i].val,v[i].lim);
  60.         fost[i][0]=1;
  61.         for(j=t;j<=8785;j+=t){
  62.             dp[i][j]=dp[i-1][j];
  63.             fost[i][j]=fost[i-1][j];
  64.             if(j<=v[i].lim && fost[i-1][j-t]==1){
  65.                 fost[i][j]=1;//printf("[%d %d %d %d]  ",i,j,dp[i-1][j-t]+v[i].val,dp[i][j]);
  66.                 if(dp[i-1][j-t]+v[i].val>dp[i][j]){
  67.                      dp[i][j]=dp[i-1][j-t]+v[i].val;
  68.                      cr2[i][j]=1;
  69.  
  70.                 }
  71.  
  72.             }
  73.         }
  74.         //printf("\n");
  75.     }
  76.     max1=ci=0;
  77.     for(i=0;i<=8785;i+=t){
  78.         if(max1<dp[n][i]){
  79.             max1=dp[n][i];
  80.             ci=i;
  81.             //printf("%d %d\n",i,dp[n][i]);
  82.         }
  83.     }
  84.     //printf("%d ",max1);
  85.     cout<<sum-max1<<"\n";
  86.     j=ci;
  87.     for(i=n;i>=1;i--){
  88.         if(cr2[i][j]==1){
  89.             j-=t;
  90.             frv[i]=1;
  91.             rasp.push_back(v[i].ind);
  92.         }
  93.     }
  94.     reverse(rasp.begin(),rasp.end());
  95.     for(i=0;i<rasp.size();i++){
  96.         cout<<rasp[i]<<" ";
  97.     }
  98.     for(i=1;i<=n;i++){
  99.         if(frv[i]==0){
  100.             cout<<v[i].ind<<" ";
  101.         }
  102.     }
  103.     return 0;
  104. }
  105.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement