Submission #127248

#	Time	Username	Problem	Language	Result	Execution time	Memory
127248		roseanne_pcy	Popeala (CEOI16_popeala)	C++14	17 / 100	2060 ms	1944 KiB

popeala

#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 (stderr)

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 / 8
• Subtask 2: 9 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 74