oj.uz

Submission #127248

# Submission time Handle Problem Language Result Execution time Memory
127248 2019-07-09T07:23:54 Z roseanne_pcy Popeala (CEOI16_popeala) C++14
17 / 100
 2000 ms 1944 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;

const int maxn = 2e4+5;
const int maxt = 55;

int n, t, s; 

ll pts[maxn];
ll foo[maxt][maxn];
ll dp[maxt][maxn];

int f(int i, int j)
{
	int ans = 0;
	for(int p = 1; p<= n; p++)
	{
		if(foo[p][j]-foo[p][i-1] == j-i+1) ans += pts[j]-pts[i-1];
	}
	return ans;
}

void solve(int k, int L, int R, int i, int j)
{
	if(L> R) return;
	int M = (L+R)/2;
	pair<ll, int> opt = {2e9, L};
	for(int p = max(1, i-900); p<= min(M, j+900); p++)
	{
		opt = min(opt, {dp[k-1][p-1]+f(p, M), p});
	}
	dp[k][M] = opt.X;
	// printf("dp[%d][%d] = %d\n", k, M, dp[k][M]);
	solve(k, L, M-1, i, opt.Y);
	solve(k, M+1, R, opt.Y, j);
}

int main()
{
	scanf("%d %d %d", &n, &t, &s);
	for(int i = 1; i<= t; i++) scanf("%lld", &pts[i]);
	for(int i = 1; i<= t; i++) pts[i] += pts[i-1];
	for(int i = 1; i<= n; i++)
	{
		char bar[maxn]; scanf("%s", bar+1);
		for(int j = 1; j<= t; j++) foo[i][j] = bar[j]-'0';
		for(int j = 1; j<= t; j++) foo[i][j] += foo[i][j-1];
	}
	for(int i = 1; i<= t; i++) dp[1][i] = f(1, i);
	dp[1][0] = 1e18;
	for(int i = 2; i<= s; i++)
	{
		dp[i][0] = 1e18;
		solve(i, 1, t, 1, t);
	}
	for(int i = 1; i<= s; i++) printf("%lld\n", dp[i][t]);
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &t, &s);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
popeala.cpp:48:34: 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:52:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   char bar[maxn]; scanf("%s", bar+1);
                   ~~~~~^~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 504 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 517 ms 1252 KB Output is correct
2 Correct 509 ms 1352 KB Output is correct
3 Correct 467 ms 1272 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2060 ms 1944 KB Time limit exceeded
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 Correct 3 ms 504 KB Output is correct
3 Correct 517 ms 1252 KB Output is correct
4 Correct 509 ms 1352 KB Output is correct
5 Correct 467 ms 1272 KB Output is correct
6 Execution timed out 2060 ms 1944 KB Time limit exceeded
7 Halted 0 ms 0 KB -