| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1089353 | TlenekWodoru | 비스킷 담기 (IOI20_biscuits) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
//#include "biscuits.h"
using namespace std;
bitset<128>tab[2][128];
bitset<128>B;
long long count_tastiness(long long x,vector<long long>AA)
{
while(AA.size()<10){AA.push_back(0);}
vector<__int128>A;
for(auto u : AA){A.push_back(u);}
const int n=A.size();
__int128 s=0;
vector<long long>dp(n);
dp.push_back(1);
for(int i=0;i<n;i++)
{
s+=A[i]*((long long)1<<i);
__int128 u=s/x;
if(u>=((__int128)1<<(i+1)))
{
for(int j=0;j<=i;j++)
{
tab[1][j][i]=1;
}
}
else
{
for(int j=0;j<=i;j++)
{
if(u%2==0)
{
tab[0][j][i]=1;
}
else
{
tab[1][j][i]=1;
}
u>>=1;
}
}
}
for(int i=8;i>=0;i--)
{
for(int j=0;j<=8;j++)
{
cout<<tab[1][j][i]<<' ';
}
cout<<endl;
}
for(int i=n-1;i>=1;i--)
{
if(dp[i+1]!=0)
{
cout<<"dp["<<i+1<<"]="<<dp[i+1]<<endl;
for(int j=0;j<128;j++)
{
B[j]=0;
}
for(int j=i;j>=0;j--)
{
B[j]=1;
if((B|tab[0][j]).count()==0)
{
dp[j]+=dp[i+1];
}
else
{
B&=(B|tab[0][j]);
}
}
dp[0]+=dp[i+1];
}
for(int j=0;j<=i;j++)
{
tab[0][j][i]=0;
tab[1][j][i]=0;
}
}
return dp[0];
}
/**
1
3 3
5 2 1
3 2
2 1 2
**/
int main()
{
int q;
cin>>q;
vector<int> k(q);
vector<long long> x(q);
vector<vector<long long>> a(q);
vector<long long> results(q);
for (int t = 0; t < q; t++) {
cin>>k[t]>>x[t];
a[t] = vector<long long>(k[t]);
for (int i = 0; i < k[t]; i++) {
cin>>a[t][i];
}
}
for (int t = 0; t < q; t++) {
results[t] = count_tastiness(x[t], a[t]);
}
for (int t = 0; t < q; t++) {
printf("%lld\n", results[t]);
}
return 0;
}