非dp,但80pts,求助
  • 板块P1833 樱花
  • 楼主mukari
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/10/24 20:09
  • 上次更新2023/10/27 06:06:14
查看原帖
非dp,但80pts,求助
446327
mukari楼主2022/10/24 20:09

rt,是数据过水?

打的纯暴力贪心,求助为什么错(感觉好像没问题?)

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ma 3145
#define il inline
#define mod 1000007
#define inf 1145141919
using namespace std;
il ll read(){
  char ch=getchar();
  ll x=0,f=1;
  while(ch<'0'||ch>'9'){
    if(ch=='-') f=-1;
    ch=getchar();
  }
  while(ch>='0'&&ch<='9'){
    x=x*10+ch-'0';
    ch=getchar();
  }
  return x*f;
}
il void write(ll x){
  char ch[20];
  ll len=0;
  if(x<0){
    putchar((1<<5)+(1<<3)+(1<<2)+1);
    x=~x+1;
  }
  do{
    ch[len++]=x%10+(1<<4)+(1<<5);
    x/=10;
  }while(x>0);
  for(ll i=len-1;i>=0;i--) putchar(ch[i]);
  return;
}
ll n;
ll t1s,t1e,t2s,t2e;
ll del=0;
struct tim{
  ll t,v,pos;
}a[ma];
bool cmp(tim a,tim b){
  return a.t*b.v<b.t*a.v;
}
int main(){
  t1s=read(),t1e=read(),t2s=read(),t2e=read();
  del=60*(t2s-t1s)+t2e-t1e;
  n=read();
  for(ll i=1;i<=n;i++){
    a[i].t=read(),a[i].v=read(),a[i].pos=read();
    if(!a[i].pos) a[i].pos=inf;
  }
  sort(a+1,a+1+n,cmp);
  ll i=1;
  ll ans=0;
  while(1){
    if(del-a[i].t>=0&&a[i].pos>0){
      ans+=a[i].v;
      a[i].pos--;
      del-=a[i].t;
    }
    else i++;
    if(i>n) break;
  }
  write(ans),puts("");
  return 0;
} 

2022/10/24 20:09
加载中...