yicongli

Gym 313459F

Jan 24th, 2021
541
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define gc c=getchar()
  6. #define r(x) read(x)
  7. #define ll long long
  8. #define db double
  9.  
  10. template<typename T>
  11. inline void read(T&x){
  12.     x=0;T k=1;char gc;
  13.     while(!isdigit(c)){if(c=='-')k=-1;gc;}
  14.     while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
  15. }
  16.  
  17. const int N=1e4+7;
  18.  
  19. struct Task{
  20.     int s,e,a,ID;
  21. };
  22.  
  23. inline bool operator <(const Task &a,const Task &b){
  24.     return a.e<b.e;
  25. }
  26.  
  27. int pre[N];
  28. Task T[N];
  29. db w[N];
  30. db f[N];
  31. db score[N];
  32. int Rank[N];
  33.  
  34. inline bool cmp(const int &a,const int &b){
  35.     return score[a]>score[b];
  36. }
  37.  
  38. int main(){
  39.     // freopen(".in","r",stdin);
  40.     // freopen(".out","w",stdout);
  41.     int n,m;r(n),r(m);
  42.     for(int i=1;i<=n;++i){
  43.         r(T[i].s),r(T[i].e),r(T[i].a);
  44.         T[i].ID=i;
  45.     }
  46.     sort(T+1,T+n+1);
  47.     for(int i=1;i<=n;++i){
  48.         int l=0,r=i-1,mid;
  49.         while(l<=r){
  50.             mid=(l+r)>>1;
  51.             if(T[mid].e<=T[i].s)l=mid+1,pre[i]=mid;
  52.             else r=mid-1;
  53.         }
  54.     }
  55.     for(int i=1;i<=m;++i){
  56.         for(int j=1;j<=n;++j){
  57.             scanf("%lf",&w[j]);
  58.         }
  59.         for(int j=1;j<=n;++j){
  60.             f[j]=max(f[j-1],f[pre[j]]+w[T[j].ID]*T[j].a);
  61.         }
  62.         score[i]=f[n];
  63.         Rank[i]=i;
  64.     }
  65.     sort(Rank+1,Rank+m+1,cmp);
  66.     for(int i=1;i<=3;++i){
  67.         printf("%d %.2lf\n",Rank[i],score[Rank[i]]);
  68.     }
  69.     return 0;
  70. }
RAW Paste Data