Submission #608737

#	Time	Username	Problem	Language	Result	Execution time	Memory
608737		Pyqe	Popeala (CEOI16_popeala)	C++14	100 / 100	1108 ms	10144 KiB

popeala

#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define fr first
#define sc second

const long long inf=1e18;
long long n,m,d,a[20069],ps[20069],dp[20069],wg[69][20069],od[69];
bitset<20069> kd[69];
pair<long long,long long> ls[69];
deque<long long> dq[69];

int main()
{
	long long i,j,r,k,l,sz;
	char ch;
	
	scanf("%lld%lld%lld",&m,&n,&d);
	for(i=1;i<=n;i++)
	{
		scanf("%lld",a+i);
		ps[i]=ps[i-1]+a[i];
	}
	for(i=1;i<=m;i++)
	{
		for(j=1;j<=n;j++)
		{
			scanf(" %c",&ch);
			kd[i][j]=ch-'0';
		}
	}
	for(i=1;i<=n;i++)
	{
		dp[i]=inf;
	}
	for(i=1;i<=d;i++)
	{
		for(j=0;j<=m;j++)
		{
			for(r=1;r<=n;r++)
			{
				wg[j][r]=dp[r-1]-ps[r-1]*j;
			}
			dq[j].clear();
			od[j]=0;
		}
		for(j=1;j<=m;j++)
		{
			ls[j]={0,j};
		}
		dp[0]=inf;
		for(j=1;j<=n;j++)
		{
			sz=0;
			for(r=1;r<=m;r++)
			{
				l=ls[r].sc;
				if(kd[l][j])
				{
					sz++;
					ls[sz]=ls[r];
				}
			}
			for(r=1;r<=m;r++)
			{
				if(!kd[r][j])
				{
					sz++;
					ls[sz]={j,r};
				}
			}
			dp[j]=inf;
			for(r=0;r<=m;r++)
			{
				k=ls[r].fr;
				l=j;
				if(r<m)
				{
					l=ls[r+1].fr;
				}
				for(;od[r]<l;)
				{
					od[r]++;
					for(;!dq[r].empty()&&wg[r][dq[r].back()]>=wg[r][od[r]];dq[r].pop_back());
					dq[r].push_back(od[r]);
				}
				for(;!dq[r].empty()&&dq[r].front()<=k;dq[r].pop_front());
				if(!dq[r].empty())
				{
					dp[j]=min(dp[j],wg[r][dq[r].front()]+ps[j]*r);
				}
			}
		}
		printf("%lld\n",dp[n]);
	}
}

Compilation message (stderr)

popeala.cpp: In function 'int main()':
popeala.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |  scanf("%lld%lld%lld",&m,&n,&d);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
popeala.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |   scanf("%lld",a+i);
      |   ~~~~~^~~~~~~~~~~~
popeala.cpp:30:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |    scanf(" %c",&ch);
      |    ~~~~~^~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 74 / 74