oj.uz

Submission #52963

# Submission time Handle Problem Language Result Execution time Memory
52963 2018-06-27T09:47:07 Z 0^0(#1376) Popeala (CEOI16_popeala) C++11
0 / 100
 2000 ms 18772 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, t, s;
const ll inf = 0x3f3f3f3f3f3f3f3f;

int p[20005];
int r[55][20005];
int sum[20005];
int q[20005][55];
ll dp[2][55][20005];
int rr[55];
int LL[55];
deque<int> dq[55];
void myassert(bool state) {
	if (state)return;
	while (true);
}
long long query(int bit, int idx, int l, int r) {
	myassert(rr[idx] <= r);
	myassert(LL[idx] <= l);
	for (int i = rr[idx]; i < r; i++) {
		while (!dq[idx].empty() && dp[bit][idx][dq[idx].back()] >= dp[bit][idx][i])dq[idx].pop_back();
		dq[idx].push_back(i);
	}
	rr[idx] = r;
	LL[idx] = l;
	while (!dq[idx].empty() && dq[idx].front() < l)dq[idx].pop_front();
	if (l >= r||dq[idx].empty())return inf;
	return dp[bit][idx][dq[idx].front()];
}
void solve(int k) {
	int now = k & 1;
	int pre = 1 - now;
	for (int i = 0; i <= n; i++) {
		dp[now][i][0] = inf;
		dq[i].clear();
		rr[i] = 0;
		LL[i] = 0;
	}
	for (int i = 1; i <= t; i++) {
		int c = n;
		long long val = inf;
		int ri = i;
		for (int j = 0; j<n; j++) {
			int le = ri - q[i][j];
			val = min(val, query(pre, c, le, ri) + c * sum[i]);
			c--;
			ri = le;
		}
		val = min(val, query(pre, c, 0, ri));
		for (int j = 0; j <= n; j++)
			dp[now][j][i] = val - j * sum[i];
		if (i == t) printf("%lld\n", val);
	}
}
int main() {
	scanf("%d%d%d", &n, &t, &s);
	for (int i = 1; i <= t; i++) {
		scanf("%d", &p[i]);
		sum[i] = sum[i - 1] + p[i];
	}
	for (int i = 0; i < n; i++) {
		int cnt = 0;
		for (int j = 1; j <= t; j++) {
			scanf("%1d", &r[i][j]);
			if (r[i][j])cnt++;
			else cnt = 0;
			q[j][i] = cnt;
		}
	}
	for (int i = 1; i <= t; i++) {
		sort(q[i], q[i] + n);
		for (int j = 1; j < n; j++)
			q[i][j] -= q[i][j - 1];
	}
	memset(dp, 0x3f, sizeof(dp));
	for (int i = 0; i <= n; i++)
		dp[0][i][0] = 0;
	for (int i = 1; i <= s; i++)
		solve(i);
	return 0;
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:58: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:60:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &p[i]);
   ~~~~~^~~~~~~~~~~~~
popeala.cpp:66:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%1d", &r[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 17656 KB Output is correct
2 Execution timed out 2062 ms 17768 KB Time limit exceeded

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2076 ms 18092 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2065 ms 18772 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 17656 KB Output is correct
2 Execution timed out 2062 ms 17768 KB Time limit exceeded