oj.uz

Submission #608737

# Submission time Handle Problem Language Result Execution time Memory
608737 2022-07-27T09:48:23 Z Pyqe Popeala (CEOI16_popeala) C++14
100 / 100
 1108 ms 10144 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 596 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 852 KB Output is correct
2 Correct 24 ms 904 KB Output is correct
3 Correct 27 ms 852 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 1608 KB Output is correct
2 Correct 172 ms 1964 KB Output is correct
3 Correct 221 ms 2612 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 34 ms 852 KB Output is correct
4 Correct 24 ms 904 KB Output is correct
5 Correct 27 ms 852 KB Output is correct
6 Correct 115 ms 1608 KB Output is correct
7 Correct 172 ms 1964 KB Output is correct
8 Correct 221 ms 2612 KB Output is correct
9 Correct 306 ms 3808 KB Output is correct
10 Correct 469 ms 4764 KB Output is correct
11 Correct 933 ms 9676 KB Output is correct
12 Correct 947 ms 10144 KB Output is correct
13 Correct 1026 ms 10088 KB Output is correct
14 Correct 1108 ms 10100 KB Output is correct
15 Correct 1030 ms 10084 KB Output is correct