oj.uz

Submission #129987

# Submission time Handle Problem Language Result Execution time Memory
129987 2019-07-13T17:53:28 Z TadijaSebez Popeala (CEOI16_popeala) C++11
100 / 100
 341 ms 14840 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8568 KB Output is correct
2 Correct 9 ms 8696 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 8828 KB Output is correct
2 Correct 17 ms 8824 KB Output is correct
3 Correct 17 ms 8824 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 9340 KB Output is correct
2 Correct 68 ms 9720 KB Output is correct
3 Correct 73 ms 9976 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8568 KB Output is correct
2 Correct 9 ms 8696 KB Output is correct
3 Correct 18 ms 8828 KB Output is correct
4 Correct 17 ms 8824 KB Output is correct
5 Correct 17 ms 8824 KB Output is correct
6 Correct 51 ms 9340 KB Output is correct
7 Correct 68 ms 9720 KB Output is correct
8 Correct 73 ms 9976 KB Output is correct
9 Correct 89 ms 10780 KB Output is correct
10 Correct 151 ms 11512 KB Output is correct
11 Correct 229 ms 14768 KB Output is correct
12 Correct 246 ms 14840 KB Output is correct
13 Correct 321 ms 14840 KB Output is correct
14 Correct 317 ms 14820 KB Output is correct
15 Correct 341 ms 14840 KB Output is correct