Submission #127672

#	Time	Username	Problem	Language	Result	Execution time	Memory
127672		TadijaSebez	Popeala (CEOI16_popeala)	C++11	17 / 100	2051 ms	3064 KiB

popeala

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int K=52;
const int N=20050;
const ll inf=1e18;
int n,t,s;
ll dp[2][N],sum[K][N],pts[N];
char res[K][N];
int go[K][N];
ll Get(int l, int r)
{
	ll s=pts[r]-pts[l-1],cnt=0;
	for(int i=1;i<=n;i++)
	{
		if(sum[i][r]-sum[i][l-1]==r-l+1) cnt++;
	}
	return s*cnt;
}
const int M=2*N;
int root,tsz,ls[M],rs[M];
ll mn[M],lzy[M];
void Build(int &c, int ss, int se, int x)
{
	c=++tsz;lzy[c]=0;
	if(ss==se){ mn[c]=dp[x][ss-1];return;}
	int mid=ss+se>>1;
	Build(ls[c],ss,mid,x);
	Build(rs[c],mid+1,se,x);
	mn[c]=min(mn[ls[c]],mn[rs[c]]);
}
void Add(int c, int ss, int se, int qs, int qe, ll x)
{
	if(qs>qe || qs>se || ss>qe) return;
	if(qs<=ss && qe>=se){ mn[c]+=x;lzy[c]+=x;return;}
	int mid=ss+se>>1;
	Add(ls[c],ss,mid,qs,qe,x);
	Add(rs[c],mid+1,se,qs,qe,x);
	mn[c]=min(mn[ls[c]],mn[rs[c]])+lzy[c];
}
ll Get(int c, int ss, int se, int qs, int qe)
{
	if(qs>qe || qs>se || ss>qe) return inf;
	if(qs<=ss && qe>=se) return mn[c];
	int mid=ss+se>>1;
	return min(Get(ls[c],ss,mid,qs,qe),Get(rs[c],mid+1,se,qs,qe))+lzy[c];
}
void Solve(int x)
{
	Build(root,1,t,x^1);
	for(int i=1;i<=t;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(res[j][i]=='1') Add(root,1,t,go[j][i],i,pts[i]);
			else for(int k=i-1;res[j][k]=='1';k--) Add(root,1,t,go[j][k],k,-pts[k]);
		}
		dp[x][i]=Get(root,1,t,1,i);
	}
	for(int i=1;i<=tsz;i++) ls[i]=rs[i]=0;
	tsz=root=0;
}
int main()
{
	scanf("%i %i %i",&n,&t,&s);
	for(int i=1;i<=t;i++) scanf("%lld",&pts[i]);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",res[i]+1);
		for(int j=1;j<=t;j++)
		{
			sum[i][j]=sum[i][j-1]+(res[i][j]=='1');
			if(res[i][j]=='1')
			{
				if(res[i][j-1]=='1') go[i][j]=go[i][j-1];
				else go[i][j]=j;
			}
		}
	}
	for(int i=0;i<2;i++) for(int j=0;j<=t;j++) dp[i][j]=inf;
	dp[0][0]=0;
	for(int i=1;i<=s;i++)
	{
		for(int j=0;j<=t;j++) dp[i&1][j]=inf;
		Solve(i&1);
		printf("%lld\n",dp[i&1][t]);
	}
	return 0;
}

Compilation message (stderr)

popeala.cpp: In function 'void Build(int&, int, int, int)':
popeala.cpp:27:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
popeala.cpp: In function 'void Add(int, int, int, int, int, long long int)':
popeala.cpp:36:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
popeala.cpp: In function 'long long int Get(int, int, int, int, int)':
popeala.cpp:45:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
popeala.cpp: In function 'int main()':
popeala.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i %i",&n,&t,&s);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
popeala.cpp:66:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=t;i++) scanf("%lld",&pts[i]);
                        ~~~~~^~~~~~~~~~~~~~~~
popeala.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",res[i]+1);
   ~~~~~^~~~~~~~~~~~~~~

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