oj.uz

Submission #90740

# Submission time Handle Problem Language Result Execution time Memory
90740 2018-12-24T08:11:11 Z IOrtroiii Popeala (CEOI16_popeala) C++14
26 / 100
 2000 ms 136340 KB 
#include <bits/stdc++.h>
using namespace std;

int n, t, s;
long long a[20005];
vector<int> go[20005];
long long f[55][20005];
char board[55][20005];

template<class num_t> 
struct range {
	num_t a[20005];
	num_t f[15][20005];
	void upd(int u,num_t v) {
		a[u] = v;
	}
	void build() {
		for (int i = 0; i <= t; ++i) f[0][i] = a[i];
		for (int i = 1; i <= 14; ++i) {
			for (int j = 0; j + (1 << i) - 1 <= t; ++j) {
				f[i][j] = min(f[i - 1][j], f[i - 1][j + (1 << (i - 1))]);
			}
		}
	}
	num_t get(int l,int r) {
		int LG = __lg(r - l + 1);
		return min(f[LG][l], f[LG][r - (1 << LG) + 1]);
	}
};

range<long long> rmq[55];

int main() {
	scanf("%d %d %d", &n, &t, &s);
	for (int i = 1; i <= t; ++i) {
		scanf("%lld", a + i);
		a[i] += a[i - 1];
	}
	for (int i = 0; i < n; ++i) {
		scanf("%s", board[i] + 1);
	}
	for (int i = 0; i < n; ++i) {
		go[0].push_back(0);
	}
	for (int i = 1; i <= t; ++i) {
		for (int j = 0; j < n; ++j) {
			if (board[j][i] == '0') {
				go[i].push_back(i);
			} else {
				go[i].push_back(go[i - 1][j]);
			}
		} 
	}
	for (int i = 0; i <= t; ++i) {
		sort(go[i].begin(), go[i].end());
	}
	for (int i = 0; i <= s; ++i) {
		for (int j = 0; j <= t; ++j) {
			f[i][j] = 1e18;
		}
	}
	f[0][0] = 0;
	for (int id = 0; id < s; ++id) {
		for (int l = 0; l <= t; ++l) {
			for (int num = 0; num <= n; ++num) {
				rmq[num].upd(l, f[id][l] - a[l] * num);
			}
		}
		for (int num = 0; num <= n; ++num) {
			rmq[num].build();
		}
		for (int r = 0; r <= t; ++r) {
			if (go[r].back() != r) go[r].push_back(r);
			if (go[r].front()) {
				f[id + 1][r] = rmq[0].get(0, go[r].front() - 1);
			}
			for (int num = 1; num < int(go[r].size()); ++num) {
				if (go[r][num] > go[r][num - 1]) {
					f[id + 1][r] = min(f[id + 1][r], rmq[num].get(go[r][num - 1], go[r][num] - 1) + a[r] * num);
				}
			}
		}
	}
	for (int i = 1; i <= s; ++i) {
		printf("%lld\n", f[i][t]);
	}
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:34: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:36:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", a + i);
   ~~~~~^~~~~~~~~~~~~~~
popeala.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", board[i] + 1);
   ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 5800 KB Output is correct
2 Correct 26 ms 5800 KB Output is correct
3 Correct 26 ms 5984 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 15284 KB Output is correct
2 Correct 188 ms 20864 KB Output is correct
3 Correct 289 ms 26972 KB Output is correct

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 888 KB Output is correct
2 Correct 3 ms 2432 KB Output is correct
3 Correct 26 ms 5800 KB Output is correct
4 Correct 26 ms 5800 KB Output is correct
5 Correct 26 ms 5984 KB Output is correct
6 Correct 147 ms 15284 KB Output is correct
7 Correct 188 ms 20864 KB Output is correct
8 Correct 289 ms 26972 KB Output is correct
9 Correct 504 ms 43320 KB Output is correct
10 Correct 797 ms 56616 KB Output is correct
11 Correct 1760 ms 129628 KB Output is correct
12 Correct 1952 ms 135144 KB Output is correct
13 Execution timed out 2057 ms 136340 KB Time limit exceeded
14 Halted 0 ms 0 KB -