QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#866079#9222. Price ComboHanghangWA 0ms19432kbC++201.4kb2025-01-22 11:37:272025-01-22 11:37:28

Judging History

你现在查看的是最新测评结果

  • [2025-01-22 11:37:28]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:19432kb
  • [2025-01-22 11:37:27]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=4e5+3;
ll n,tot;
array<array<ll,2>,2>f[N];
array<ll,3>a[N],num[N]; 
map<array<ll,3>,ll>mp;
void Min(ll &x,ll y){if(x>y)x=y;}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i][0];
	for(int i=1;i<=n;i++)cin>>a[i][1],a[i][2]=a[i][0]>a[i][1];
	for(int i=1;i<=n;i++)
	{
		ll x=a[i][0],y=a[i][1],o=a[i][2];
		mp[{x,o,i}]=mp[{y,o^1,i}]=1;
	}
	for(auto &p:mp)p.second=++tot,num[tot]=p.first;
	memset(f,0x3f,sizeof(f));f[tot+1][0][0]=0;
	for(int t=tot;t>=1;t--)
	{
		int id=num[t][2];
		if(num[t][1]){f[t]=f[t+1];continue;};
		if(!a[id][2])for(int x:{0,1})for(int y:{0,1})f[t][x][y]=f[t+1][x^1][y]+(x==1)*a[id][0];
		else for(int x:{0,1})for(int y:{0,1})f[t][x][y]=f[t+1][x][y^1]+(y==1)*a[id][1];
		int j=mp[{a[id][a[id][2]^1],1,id}];
		auto F=f[j+1];
		for(int k=j;k>t;k--)if(!num[k][1])
		{
			id=num[k][2];auto G=F;
			if(!a[id][2])for(int x:{0,1})for(int y:{0,1})F[x][y]=G[x^1][y]+(x==1)*a[id][0];
			else for(int x:{0,1})for(int y:{0,1})F[x][y]=G[x][y^1]+(y==1)*a[id][1];
		}
		id=num[t][2];
		if(!a[id][2])for(int x:{0,1})for(int y:{0,1})Min(f[t][x][y],f[t+1][x^1][y]+(x==1)*a[id][1]);
		else for(int x:{0,1})for(int y:{0,1})Min(f[t][x][y],f[t+1][x][y^1]+(y==1)*a[id][0]);
	}
	cout<<min({f[1][0][0],f[1][0][1],f[1][1][0],f[1][1][1]});
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 19432kb

input:

7
10 12 19 99 10 8 49
9 14 15 199 11 7 19

output:

137

result:

wrong answer 1st lines differ - expected: '131', found: '137'