QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#479965 | #8005. Crossing the Border | tarjen | WA | 87ms | 12416kb | C++20 | 2.9kb | 2024-07-15 23:42:33 | 2024-07-15 23:42:33 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N=11;
const int mod=998244353;
void add(int &x,int y){
if((x+=y)>=mod)x-=mod;
}
struct info{
int x,t;
string str(){
return "("+to_string(x)+","+to_string(t)+")";
}
};
info& operator+=(info &x,const info y){
if(y.x<x.x)x=y;
else if(y.x==x.x)add(x.t,y.t);
return x;
}
info operator+(info x,const int y){
x.x+=y;
return x;
}
info dp[1<<N][1<<N];
int a1[N],b1[N];
int a2[N],b2[N];
int suma1[1<<N],suma2[1<<N];
int sumb1[1<<N],sumb2[1<<N];
vector<int> ve1[1<<N],ve2[1<<N];
int main()
{
int n,w;cin>>n>>w;
vector<pair<int,int>> p(n);
for(int i=0;i<n;i++)cin>>p[i].second>>p[i].first;
sort(p.begin(),p.end());
reverse(p.begin(),p.end());
if(n==1){
cout<<p[0].first<<" "<<1<<"\n";
return 0;
}
int m=n/2;
n-=m;
for(int i=0;i<n;i++)a1[i]=p[i].second,b1[i]=p[i].first;
for(int i=0;i<m;i++)a2[i]=p[i+n].second,b2[i]=p[i+n].first;
for(int i=0;i<(1<<n);i++)
for(int j=0;j<(1<<m);j++)dp[i][j]={(int)2e9,0};
for(int i=1;i<(1<<n);i++)suma1[i]=suma1[i^(1<<__builtin_ctz(i))]+a1[__builtin_ctz(i)],sumb1[i]=b1[__builtin_ctz(i)];
for(int i=1;i<(1<<m);i++)suma2[i]=suma2[i^(1<<__builtin_ctz(i))]+a2[__builtin_ctz(i)],sumb2[i]=b2[__builtin_ctz(i)];
dp[0][0]={0,1};
for(int i=1;i<(1<<m);i++){
for(int j=i;j;j=(j-1)&i)if(suma2[j]<=w){
dp[0][i]+=(dp[0][i^j]+sumb2[j]);
}
}
for(int i=0;i<(1<<n);i++){
ve1[i].push_back(0);
for(int j=(i-1)&i;j;j=(j-1)&i)if(suma1[j^i]<=w){
ve1[i].push_back(j);
}
sort(ve1[i].begin(),ve1[i].end(),[&](int x,int y){
return suma1[x^i]<suma1[y^i];
});
}
for(int i=0;i<(1<<m);i++){
int p=((1<<m)-1)^i;
ve2[i].push_back(i);
for(int j=p;j;j=(j-1)&p)if(suma2[j]<=w){
ve2[i].push_back(j^i);
}
sort(ve2[i].begin(),ve2[i].end(),[&](int x,int y){
return suma2[x^i]>suma2[y^i];
});
}
for(int i=1;i<(1<<n);i++){
for(int j=0;j<(1<<m);j++){
info mi={(int)2e9,1};
auto it1=ve1[i].begin();
auto it2=ve2[j].begin();
while(it2!=ve2[j].end()&&suma1[(*it1)^i]+suma2[(*it2)^j]>w)it2++;
for(;it2!=ve2[j].end();it2++){
while(it1!=ve1[i].end()&&suma1[(*it1)^i]+suma2[(*it2)^j]<=w){
// cout<<dp[*it1][j].x<<" "<<sumb1[(*it1)^i]<<endl;
mi+=(dp[*it1][j]+sumb1[(*it1)^i]);
it1++;
}
if(*it2!=j)dp[i][*it2]+=mi;
// cout<<"i="<<i<<" j="<<j<<" it1="<<*it1<<" *it2="<<*it2<<" mi="<<mi.str()<<endl;
}
// cout<<"i="<<i<<" j="<<j<<" ("<<dp[i][j].x<<","<<dp[i][j].t<<")"<<endl;
}
}
cout<<dp[(1<<n)-1][(1<<m)-1].x<<" ";
cout<<dp[(1<<n)-1][(1<<m)-1].t<<"\n";
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3660kb
input:
5 5 3 5 1 4 2 3 2 2 2 1
output:
9 4
result:
ok 2 number(s): "9 4"
Test #2:
score: -100
Wrong Answer
time: 87ms
memory: 12416kb
input:
18 10000000 956231 904623 1692946 1796774 1081323 1170319 3218792 2542661 3183376 3037270 1869132 1442561 35436 35018 1564635 1939950 1847344 2006043 755870 899310 1671882 2057413 1369264 1338951 3132483 3504034 2056224 1825640 1840949 1562071 1514040 1405352 2300821 2421801 2466540 3004920
output:
9391997 186
result:
wrong answer 2nd numbers differ - expected: '70', found: '186'