oj.uz

Submission #52912

# Submission time Handle Problem Language Result Execution time Memory
52912 2018-06-27T07:17:27 Z 0^0(#1376) Popeala (CEOI16_popeala) C++11
26 / 100
 2000 ms 39716 KB 
#include <bits/stdc++.h>
using namespace std;
int n, t, s;
const int inf = 2e9 + 5;
struct SGT {
	int tree[20005 << 2];
	int sz;
	SGT() {
		for (int i = 0; i < (20005 << 2); i++)
			tree[i] = inf;
		sz = 1;
		while (sz < 20005)sz *= 2;
	}
	void init() {
		for (int i = 0; i < (20005 << 2); i++)
			tree[i] = inf;
	}
	void update(int idx, int val) {
		idx += sz;
		tree[idx] = val;
		idx /= 2;
		while (idx) {
			tree[idx] = min(tree[idx * 2], tree[idx * 2 + 1]);
			idx /= 2;
		}
	}
	int query(int le, int ri) {
		le += sz;
		ri += sz;
		int ret = inf;
		while (le <= ri) {
			if (le & 1)ret = min(ret, tree[le++]);
			if (!(ri & 1))ret = min(ret, tree[ri--]);
			le /= 2;
			ri /= 2;
		}
		return ret;
	}
};
int p[20005];
int r[55][20005];
int sum[20005];
vector<int> q[20005];
SGT dp[2][55];
void solve(int k) {
	int now = k & 1;
	int pre = 1 - now;
	for (int i = 0; i <= n; i++)dp[now][i].init();
	for (int i = 1; i <= t; i++) {
		int c = n;
		int val = inf;
		int ri = i;
		int px = 0;
		for (auto x : q[i]) {
			int le = ri - (x - px) + 1;
			int temp = min((long long)inf, dp[pre][c].query(le - 1, ri - 1) + (long long)c*sum[i]);
			c--;
			ri = le - 1;
			val = min(val, temp);
			px = x;
		}
		int temp = min((long long)inf, dp[pre][c].query(0, ri - 1) + (long long)c*sum[i]);
		val = min(val, temp);
		for (int j = 0; j <= n; j++)
			dp[now][j].update(i, min((long long)inf, val - (long long)j * sum[i]));
		if (i == t) printf("%d\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].push_back(cnt);
		}
	}
	for (int i = 1; i <= t; i++)
		sort(q[i].begin(), q[i].end());
	for (int i = 0; i <= n; i++)
		dp[0][i].update(0, 0);
	for (int i = 1; i <= s; i++)
		solve(i);
	return 0;
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:70: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:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &p[i]);
   ~~~~~^~~~~~~~~~~~~
popeala.cpp:78: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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 35320 KB Output is correct
2 Correct 57 ms 35544 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 35744 KB Output is correct
2 Correct 262 ms 35808 KB Output is correct
3 Correct 263 ms 35824 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 628 ms 36684 KB Output is correct
2 Correct 870 ms 37104 KB Output is correct
3 Correct 1048 ms 37576 KB Output is correct

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 35320 KB Output is correct
2 Correct 57 ms 35544 KB Output is correct
3 Correct 261 ms 35744 KB Output is correct
4 Correct 262 ms 35808 KB Output is correct
5 Correct 263 ms 35824 KB Output is correct
6 Correct 628 ms 36684 KB Output is correct
7 Correct 870 ms 37104 KB Output is correct
8 Correct 1048 ms 37576 KB Output is correct
9 Correct 1732 ms 38768 KB Output is correct
10 Execution timed out 2062 ms 39716 KB Time limit exceeded
11 Halted 0 ms 0 KB -