| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 92155 | Bodo171 | Parrots (IOI11_parrots) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "encoder.h"
#include "encoderlib.h"
#include <iostream>
using namespace std;
const int base=(1<<8);
const int nm=325,mm=275,cifmax=600;
static int dp[nm][mm][cifmax],sum[nm][mm][cifmax];
static int cost[cifmax],A[cifmax],aux[cifmax];
static int unu[cifmax],zr[cifmax];
static int v[nm];
static int i,j,poz,p,n,m,k;
void add(int A[],int B[])
{
A[0]=max(A[0],B[0]);
for(int idx=1;idx<=A[0];idx++)
{
A[idx]+=B[idx];
if(A[idx]>=base)
{
A[idx+1]+=(A[idx]>>8);
if(idx+1>A[0])
A[0]=idx+1;
A[idx]&=(base-1);
}
}
}
void memc(int A[],int B[])
{
for(int idx=1;idx<=A[0];idx++)
A[idx]=0;
A[0]=0;
for(int idx=0;idx<=B[0];idx++)
A[idx]=B[idx];
}
void prc_dp()
{
for(k=0;k<cifmax;k++)
unu[k]=zr[k]=0;
for(i=0;i<=n+1;i++)
for(j=0;j<=m+1;j++)
for(k=0;k<cifmax;k++)
dp[i][j][k]=sum[i][j][k]=0;
unu[0]=unu[1]=1;
for(i=n;i>=1;i--)
for(j=m;j>=0;j--)
{
add(dp[i][j],sum[i+1][j]);
if(i==n)
add(dp[i][j],unu);
add(sum[i][j],sum[i][j+1]);
add(sum[i][j],dp[i][j]);
}
}
bool mmic(int X[],int Y[])
{
if(X[0]<Y[0]) return 1;
if(X[0]>Y[0]) return 0;
for(int idx=X[0];idx>=1;idx--)
{
if(X[idx]<Y[idx]) return 1;
if(X[idx]>Y[idx]) return 0;
}
return 0;
}
void get_kth()
{
memc(cost,zr);memc(aux,zr);
for(poz=1;poz<=n;poz++)
{
p=v[poz-1];
memc(aux,cost);
for(int ok=1;ok!=0;)
{
add(aux,dp[poz][p]);
if(mmic(aux,A)) memc(cost,aux);
else v[poz]=p,ok=0;
p++;
}
send(v[poz]);
}
}
void encode(int N, int M[])
{
n=5*N;
m=255;
memc(A,zr);
for(i=0;i<N;i++)
{
A[i+1]=M[i];
if(A[i+1]) A[0]=i+1;
}
prc_dp();
get_kth();
}