Advertisement
Patrickmeme

Venus - signal 11

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