数据是否过水
查看原帖
数据是否过水
531930
Southern_Dynasty楼主2022/9/28 19:22

RT.

我这代码样例都过不去,但是一交直接过了。

#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma GCC optimize("Ofast")
#define gt getchar
#define pt putchar
#define y1 y233
#define rep(i,a,b,k) for(int (i)=(a),(_)=(b);(i)<=(_);(i)+=(k))
#define per(i,a,b,k) for(int (i)=(a),(_)=(b);(i)>=(_);(i)-=(k))
#define edgerep(i,h,u,e) for(int (i)=h[(u)];(i);(i)=e[(i)].nxt)
typedef long long ll;
//typedef __int128 lll;
typedef unsigned long long ull;
const int N=1005;
const int M=5005;
using namespace std;
//using namespace __gnu_pbds;
inline bool __(char ch){return ch>=48&&ch<=57;}
inline int read(){
   	int x=0;bool sgn=0;char ch=gt();
   	while(!__(ch)){sgn|=(ch=='-');ch=gt();}
   	while(__(ch)){x=(x<<1)+(x<<3)+(ch-'0');ch=gt();}
	return sgn?-x:x;
}
inline void print(int x){
	static char st[70];short top=0;
	if(x<0)pt('-'),x=-x;
    do{st[++top]=(x%10+'0'),x/=10;}while(x);
    while(top)pt(st[top--]);
}
inline void printsp(int x){
	static char st[70];short top=0;
	if(x<0)pt('-'),x=-x;
    do{st[++top]=(x%10+'0'),x/=10;}while(x);
    while(top)pt(st[top--]);pt(32);
}
inline void println(int x){
	static char st[70];short top=0;
	if(x<0)pt('-'),x=-x;
    do{st[++top]=(x%10+'0'),x/=10;}while(x);
    while(top)pt(st[top--]);pt(10);
}
inline void put_string(string s){
	int siz=s.size();
	rep(i,0,siz-1,1) pt(s[i]);
	printf("\n");
}
int m,t[N],cnt[N],dp[N][M],val[N][N],tim[N][N];
//设dp[i][j]表示i节点在j时间内最多能偷到的画的数量 
void build(int i){
	t[i]=read()*2,cnt[i]=read();
	if(!cnt[i]){
		build(i<<1);
		build(i<<1|1);
	}else{
		rep(j,1,cnt[i],1){
			val[i][j]=read();
			tim[i][j]=read();
		}
	}
}
void dfs(int u,int T){
	if(!cnt[u]){
		int l=(u<<1),r=((u<<1)|1);
		dfs(l,T+t[l]);
		dfs(r,T+t[r]);
		rep(i,0,m-T-1,1) rep(j,0,m-T-i,1) dp[u][T+i+j]=max(dp[u][T+i+j],dp[l][T+i]+dp[r][T+j]);
	}else{
		int now=T;
		rep(i,1,cnt[u],1){
			now+=tim[u][i];
			if(now>=m)return;
			dp[u][now]=dp[u][now-tim[u][i-1]]+val[u][i];
		}
	}
}
signed main(){
	m=read()-1;
	build(1);
	dfs(1,t[1]);
	println(dp[1][m]);
	return 0;
}
2022/9/28 19:22
加载中...