列表

详情

NC53274. 两道料理

描述

题目译自 JOISC 2019 Day2 T2「ふたつの料理 / Two Dishes」
厨师比太郎正在参加一个厨艺比赛。在这场比赛中参赛者要烹饪两道料理：IOI盖饭和JOI咖喱。
IOI盖饭的烹饪过程中需要N个步骤。第步的用时是A_i分钟，最初他只能进行第1步，想要进行第步的条件是已经完成了第i-1步。
JOI咖喱的烹饪过程中需要M个步骤。第步的用时是B_j分钟，最初他只能进行第1步，想要进行第步的条件是已经完成了第j-1步。
做料理过程中需要专心致志，所以当他开始进行一个步骤时，就不能中断。当完成了一个步骤，他也可以选择进行另一道料理的下一个步骤。比赛开始后，在两道料理都完成之前，他不能停下来休息。
在这场比赛中，参赛者会按照接下来的方式得到艺术感的打分：
  • 如果他在比赛的前分钟内完成了IOI盖饭的第i个步骤，那么从中他会得到P_i点的分数，分数有可能是负的。
  • 如果他在比赛的前分钟内完成了JOI咖喱的第j个步骤，那么从中他会得到Q_j点的分数，分数有可能是负的。
请你帮助比太郎设计做料理过程，最大化他做料理的艺术感评分。

输入描述

从标准输入中读取数据。
第一行两个整数N,M。
接下来N行，每行三个整数A_i,S_i,P_i。
接下来M行，每行三个整数B_j,T_j,Q_j。

输出描述

输出数据到标准输出中。
一个整数，表示比太郎能得到的最高艺术感评分。

示例1

输入: 

4 3
2 1 1
3 8 1
2 13 1
1 13 1
3 6 1
2 11 1
2 15 1

输出: 

6

说明:

比太郎可以按照此方案进行烹饪：
1.进行JOI咖喱的第1个步骤，完成时已经距离比赛开始3分钟，还在6分钟内，他得到1分。
2.进行IOI盖饭的第1个步骤，完成时已经距离比赛开始5分钟，不在1分钟内，他没有得分。
3.进行IOI盖饭的第2个步骤，完成时已经距离比赛开始8分钟，还在8分钟内，他得到1分。
4.进行JOI咖喱的第2个步骤，完成时已经距离比赛开始10分钟，还在11分钟内，他得到1分。
5.进行IOI盖饭的第3个步骤，完成时已经距离比赛开始12分钟，还在13分钟内，他得到1分。
6.进行IOI盖饭的第4个步骤，完成时已经距离比赛开始13分钟，还在13分钟内，他得到1分。
7.进行JOI咖喱的第3个步骤，完成时已经距离比赛开始15分钟，还在15分钟内，他得到1分。
比太郎总共得到6分，他无法得到更高的分数。

示例2

输入: 

5 7
16 73 16
17 73 10
20 73 1
14 73 16
18 73 10
3 73 2
10 73 7
16 73 19
12 73 4
15 73 15
20 73 14
15 73 8

输出: 

63

说明:

这组样例满足子任务1的限制。

示例3

输入: 

9 11
86 565 58
41 469 -95
73 679 28
91 585 -78
17 513 -63
48 878 -66
66 901 59
72 983 -70
68 1432 11
42 386 -87
36 895 57
100 164 10
96 812 -6
23 961 -66
54 193 51
37 709 82
62 148 -36
28 853 22
15 44 53
77 660 -19

输出: 

99

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(clang++11) 解法, 执行用时: 3852ms, 内存消耗: 125928K, 提交时间: 2021-02-07 11:55:29 

#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
#define ll long long
ll gi(){
	ll x=0,w=1;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')w=0,ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
const int N=1e6+5;
struct node{
	int x,y;ll z;
	bool operator < (const node &b)const
		{return x<b.x;}
}a[N<<1];
int n,m,tot,pos[N<<2];
ll A[N],S[N],P[N],B[N],T[N],Q[N],val[N],ans;
set<int>Set;set<int>::iterator it;
void up(int x){pos[x]=val[pos[x<<1]]<val[pos[x<<1|1]]?pos[x<<1]:pos[x<<1|1];}
void build(int x,int l,int r){
	if(l==r){pos[x]=l;return;}int mid=l+r>>1;
	build(x<<1,l,mid);build(x<<1|1,mid+1,r);up(x);
}
void modify(int x,int l,int r,int p,ll v){
	if(l==r){
		val[l]+=v;
		if(val[l])Set.insert(l);else Set.erase(l);
		return;
	}
	int mid=l+r>>1;p<=mid?modify(x<<1,l,mid,p,v):modify(x<<1|1,mid+1,r,p,v);up(x);
}
int main(){
	n=gi();m=gi();
	for(int i=1;i<=n;++i)A[i]=A[i-1]+gi(),S[i]=gi(),P[i]=gi();
	for(int i=1;i<=m;++i)B[i]=B[i-1]+gi(),T[i]=gi(),Q[i]=gi();
	for(int i=1;i<=n;++i)
		if(A[i]<=S[i]){
			ans+=P[i];int p=upper_bound(B+1,B+m+1,S[i]-A[i])-B;
			if(p<=m)a[++tot]=(node){i-1,p,-P[i]};
		}
	for(int i=1;i<=m;++i)
		if(B[i]<=T[i]){
			int p=upper_bound(A+1,A+n+1,T[i]-B[i])-A-1;
			a[++tot]=(node){p,i,Q[i]};
		}
	a[++tot]=(node){n,1,0};
	sort(a+1,a+tot+1);build(1,1,m);
	for(int i=1,j=1;i<=tot;i=j=j+1){
		while(j<tot&&a[j+1].x==a[i].x)++j;
		if(a[i].x==n){
			for(int k=i;k<=j;++k)ans+=a[k].z;
			for(int x:Set)ans+=val[x];
			printf("%lld\n",ans);
			return 0;
		}
		for(int k=i;k<=j;++k)modify(1,1,m,a[k].y,a[k].z);
		while(val[pos[1]]<0){
			int p=pos[1];ll v=val[p];
			it=Set.find(p);++it;
			if(it!=Set.end())modify(1,1,m,*it,v);
			modify(1,1,m,p,-v);
		}
	}
}

上一题

© 2024 nowcoder.com