[数据结构与算法]哦~唔西迪西小姐

牛客网

题目描述

唔西迪西现在正处在一个冰火迷宫中，迷宫由 n 个格子组成，每个格子要么是冰之格，要么是火之格，唔西迪西刚开始可以选择从迷宫中任意一个开始走，走到第 i 个位置时会得到值为 ai的积分。（注意：唔西迪西也可以选择一个格子都不走）

如果唔西迪西当前在冰之格，那么她可以选择一个编号大于当前格子的冰之格，跳到那里。如果唔西迪西当前在火之格，那么她可以选择一个编号大于当前格子的火之格，跳到那里。如果唔西迪西目前没有格子可以走，那么结束。同时，即使存在可以跳过去的格子，唔西迪西也可以选择在任意时刻结束。

唔西迪西想最大化她的得分，于是她学会了一个超能力，她能在比赛开始的时候改变最多 m 个格子的状态，即将一个格子从冰之格变成火之格或从火之格变成冰之格，改变第ii 个格子的状态会让唔西迪西的得分减少 pi。（唔西迪西改变格子的状态后才开始挑选起点开始行动，也就是说，得分分成两部分，一部分是改变格子状态的得分，一部分是走格子的得分）

你能告诉唔西迪西她最多得几分吗

输入描述:

第一行两个正整数 n,m(1≤n,m≤10 ⁵ )。

第二行 nn个整数表示 ai。

第三行 n 个整数表示 pi (-10⁵≤ai,pi ≤10⁵) )。

第四行 n 个整数 bi ,为 0 或 1，0 表示这个格子是冰之格，1 表示这个格子是火之格。

输出描述:

一个数表示答案。

示例1

输入

3 2
1 15 9
2 5 7
1 0 1

输出

20

示例2

输入

10 3
80 86 57 69 59 52 94 74 9 63
8 32 77 64 53 49 22 68 27 63
1 0 0 0 1 0 0 1 1 1

复制

442

代码

#include "stdio.h"
#include "algorithm"
#include "iostream"
#include "string.h"
#include "string"
#include "math.h"
using namespace std;
#define ll long long
int a[100015],b[100015];
int a1[100015],a2[100015];
int ppp(int x,int y)
{
	return x>y;
}
int main()
{
	ll sum1=0,sum2=0;
	int n,m,la1=0,la2=0,k;
	cin>>n>>m;
	for(int i=1; i<=n; i++)
		cin>>a[i];
	for(int i=1; i<=n; i++)
		cin>>b[i];
	for(int i=1; i<=n; i++)
	{
		cin>>k;
		if(k==0)
		{
			if(a[i]>0)//a[i]<0时 唔西迪西不跳它 
			{
				sum1+=a[i];
				a2[la2++]=a[i]-b[i];
				a1[la1++]=-a[i]-b[i];//有用的数据是当b[i]<0&&abs(b[i])>a[i];
			}
			else if(b[i]<0)
			{
				a1[la1++]=-b[i];
				a2[la2++]=-b[i];
			}
		}
		else
		{
			if(a[i]>0)//a[i]<0时 唔西迪西不跳它 
			{
				sum2+=a[i];
				a1[la1++]=a[i]-b[i];
				a2[la2++]=-a[i]-b[i];//有用的数据是当b[i]<0&&abs(b[i])>a[i];
			}
			else if(b[i]<0)
			{
				a1[la1++]=-b[i];
				a2[la2++]=-b[i];
			}
		}
	}
	sort(a1,a1+la1,ppp);
	sort(a2,a2+la2,ppp);
	for(int i=0; i<la1; i++)
	{
		if(a1[i]<0||i>=m)
			break;
		sum1+=a1[i];
	}
	for(int i=0; i<la2; i++)
	{
		if(a2[i]<0||i>=m)
			break;
		sum2+=a2[i];
	}
	printf("%lld\n",max(sum1,sum2));
}