Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <fstream>
- #include <algorithm>
- #include <vector>
- #include <bitset>
- using namespace std;
- ifstream cin("venus.in");
- ofstream cout("venus.out");
- struct com{
- int val,lim,ind;
- } v[1001];
- bitset <1001> frv;
- bitset <1001> cr2[8785];
- vector <int> rasp;
- int dp[1001][8785];
- bool fost[1001][8785];
- string conv[]={"ianuarie","februarie","martie","aprilie","mai","iunie","iulie","august","septembrie","octombrie","noiembrie","decembrie"};
- bool cmp(com a,com b){
- if(a.lim<b.lim)
- return 1;
- return 0;
- }
- int convF(string s){
- int i,su;
- i=su=0;
- while(conv[i]!=s){
- if(i%2==0)
- su+=31;
- else if(i%2==1 && i!=1)
- su+=30;
- else
- su+=29;
- i++;
- }
- return su;
- }
- int main()
- {
- string s;
- int n,t,i,zi,h,max1,j,sum=0,ci;
- cin>>n>>t;
- for(i=1;i<=n;i++){
- v[i].ind=i;
- cin>>v[i].val>>zi>>s>>h;
- sum+=v[i].val;
- v[i].lim=(convF(s)+zi-1)*24+h;
- ///printf("%d\n",v[i].lim);
- }
- sort(v+1 ,v+n+1,cmp);
- fost[0][0]=1;
- for(i=1;i<=n;i++){
- //printf("|%d %d|",v[i].val,v[i].lim);
- fost[i][0]=1;
- for(j=t;j<=8785;j+=t){
- dp[i][j]=dp[i-1][j];
- fost[i][j]=fost[i-1][j];
- if(j<=v[i].lim && fost[i-1][j-t]==1){
- fost[i][j]=1;//printf("[%d %d %d %d] ",i,j,dp[i-1][j-t]+v[i].val,dp[i][j]);
- if(dp[i-1][j-t]+v[i].val>dp[i][j]){
- dp[i][j]=dp[i-1][j-t]+v[i].val;
- cr2[i][j]=1;
- }
- }
- }
- //printf("\n");
- }
- max1=ci=0;
- for(i=0;i<=8785;i+=t){
- if(max1<dp[n][i]){
- max1=dp[n][i];
- ci=i;
- //printf("%d %d\n",i,dp[n][i]);
- }
- }
- //printf("%d ",max1);
- cout<<sum-max1<<"\n";
- j=ci;
- for(i=n;i>=1;i--){
- if(cr2[i][j]==1){
- j-=t;
- frv[i]=1;
- rasp.push_back(v[i].ind);
- }
- }
- reverse(rasp.begin(),rasp.end());
- for(i=0;i<rasp.size();i++){
- cout<<rasp[i]<<" ";
- }
- for(i=1;i<=n;i++){
- if(frv[i]==0){
- cout<<v[i].ind<<" ";
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement