oj.uz

Submission #127647

# Submission time Handle Problem Language Result Execution time Memory
127647 2019-07-09T19:53:59 Z TadijaSebez Popeala (CEOI16_popeala) C++11
0 / 100
 118 ms 2808 KB 
#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)
{
	/*for(int i=l;i<=r;i++)
	{
		for(int j=L;j<=min(i,R);j++)
		{
			dp[x][i]=min(dp[x][i],dp[x-1][j-1]+Get(j,i));
		}
	}*/
	if(l>r) return;
	int mid=l+r>>1;
	int opt=mid;
	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

popeala.cpp: In function 'void Solve(int, int, int, int, int)':
popeala.cpp:28:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=l+r>>1;
          ~^~
popeala.cpp: In function 'int main()':
popeala.cpp:44: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:45:45: 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:48: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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 760 KB Output isn't correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 1400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 118 ms 2808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 760 KB Output isn't correct