Submission #127643

#	Time	Username	Problem	Language	Result	Execution time	Memory
127643		TadijaSebez	Popeala (CEOI16_popeala)	C++11	0 / 100	39 ms	2808 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[K][N],sum[K][N],pts[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;
}
void Solve(int x, int l, int r, int L, int R)
{
	if(l>r) return;
	int mid=l+r>>1;
	int opt;
	for(int i=L;i<=min(mid,R);i++)
	{
		if(dp[x][mid]>dp[x-1][i-1]+Get(i,mid))
		{
			opt=i;
			dp[x][mid]=dp[x-1][i-1]+Get(i,mid);
		}
	}
	Solve(x,l,mid-1,L,opt);
	Solve(x,mid+1,r,opt,R);
}
char res[K][N];
int main()
{
    scanf("%i %i %i",&n,&t,&s);
    for(int i=1;i<=t;i++) scanf("%lld",&pts[i]),pts[i]+=pts[i-1];
    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');
	}
	for(int i=0;i<=s;i++) for(int j=0;j<=t;j++) dp[i][j]=inf;
	dp[0][0]=0;
	for(int i=1;i<=s;i++) Solve(i,1,t,1,t);
	for(int i=1;i<=s;i++) printf("%lld\n",dp[i][t]);
	return 0;
}

Compilation message (stderr)

popeala.cpp: In function 'void Solve(int, int, int, int, int)':
popeala.cpp:21:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=l+r>>1;
          ~^~
popeala.cpp: In function 'int main()':
popeala.cpp:37:10: 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:38:48: 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]),pts[i]+=pts[i-1];
                           ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
popeala.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",res[i]+1);
   ~~~~~^~~~~~~~~~~~~~~
popeala.cpp: In function 'void Solve(int, int, int, int, int)':
popeala.cpp:31:7: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
  Solve(x,l,mid-1,L,opt);
  ~~~~~^~~~~~~~~~~~~~~~~

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