QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#866089#9222. Price ComboHanghangTL 1018ms64124kbC++201.4kb2025-01-22 11:49:512025-01-22 11:49:51

Judging History

This is the latest submission verdict.

  • [2025-01-22 11:49:51]
  • Judged
  • Verdict: TL
  • Time: 1018ms
  • Memory: 64124kb
  • [2025-01-22 11:49:51]
  • Submitted

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];auto G=F;
		if(!a[id][2])for(int x:{0,1})for(int y:{0,1})F[x][y]=G[x][y^1]+(y==1)*a[id][1];
		else for(int x:{0,1})for(int y:{0,1})F[x][y]=G[x^1][y]+(x==1)*a[id][0];
		for(int k=j;k>t;k--)if(!num[k][1])
		{
			id=num[k][2];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];
		}
		for(int x:{0,1})for(int y:{0,1})Min(f[t][x][y],F[x][y]);
	}
	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: 100
Accepted
time: 0ms
memory: 20072kb

input:

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

output:

131

result:

ok single line: '131'

Test #2:

score: 0
Accepted
time: 1ms
memory: 19556kb

input:

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

output:

131

result:

ok single line: '131'

Test #3:

score: 0
Accepted
time: 1018ms
memory: 64124kb

input:

199913
1212731 2525164 3210261 2457211 1013738 1931420 923123 867112 762069 2108660 108920 2491869 867107 387025 2278045 574027 1661570 820133 1274150 2001346 779766 3305537 3000211 2418643 2108660 2001343 1074820 2754411 826712 3117447 1661569 338161 1849064 3007920 3057426 468078 3252798 1274146 4...

output:

154816494865

result:

ok single line: '154816494865'

Test #4:

score: 0
Accepted
time: 284ms
memory: 62020kb

input:

200000
97216869 743886950 33071099 93740214 165915739 714765240 770423425 498199793 631193672 753722174 569396548 842251035 911607641 450531347 765200530 739362614 91640365 174209387 248940417 335559443 238573490 479206903 882783448 200485674 717481029 526848873 692757023 616376164 573933118 2566387...

output:

49954742111708

result:

ok single line: '49954742111708'

Test #5:

score: -100
Time Limit Exceeded

input:

200000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000...

output:


result: