Submission #129987

#	Time	Username	Problem	Language	Result	Execution time	Memory
129987		TadijaSebez	Popeala (CEOI16_popeala)	C++11	100 / 100	341 ms	14840 KiB

popeala

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=20050;
const int K=52;
const ll inf=1e18;
ll dp[K][N],best[K],pts[N];
int last[N][K];
char res[K][N];
int main()
{
	int n,t,s;
	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++) last[j][i]=res[i][j]=='1'?last[j-1][i]:j;
	}
    for(int j=1;j<=t;j++)
	{
		last[j][0]=j;
		sort(last[j],last[j]+n+1);
	}
	for(int i=0;i<K;i++) for(int j=0;j<N;j++) dp[i][j]=inf;
	dp[0][0]=0;
	for(int i=1;i<=s;i++)
	{
		for(int i=0;i<K;i++) best[i]=inf;
		for(int j=1;j<=t;j++)
		{
			for(int k=0;k<=n;k++)
			{
				for(int l=last[j-1][k];l<last[j][k];l++) best[k]=min(best[k],dp[i-1][l]-pts[l]*k);
				dp[i][j]=min(dp[i][j],best[k]+pts[j]*k);
			}
		}
		printf("%lld\n",dp[i][t]);
	}
	return 0;
}

Compilation message (stderr)

popeala.cpp: In function 'int main()':
popeala.cpp:13: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:14: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:17: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: 9 / 9
• Subtask 4: 74 / 74