QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#866079 | #9222. Price Combo | Hanghang | WA | 0ms | 19432kb | C++20 | 1.4kb | 2025-01-22 11:37:27 | 2025-01-22 11:37:28 |
Judging History
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'