oj.uz

Submission #90745

# Submission time Handle Problem Language Result Execution time Memory
90745 2018-12-24T08:22:01 Z IOrtroiii Popeala (CEOI16_popeala) C++14
26 / 100
 2000 ms 131764 KB 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#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:36: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:38:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", a + i);
   ~~~~~^~~~~~~~~~~~~~~
popeala.cpp:42: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 2300 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 5816 KB Output is correct
2 Correct 23 ms 5816 KB Output is correct
3 Correct 22 ms 5820 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 15164 KB Output is correct
2 Correct 223 ms 20456 KB Output is correct
3 Correct 310 ms 26448 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 2300 KB Output is correct
3 Correct 23 ms 5816 KB Output is correct
4 Correct 23 ms 5816 KB Output is correct
5 Correct 22 ms 5820 KB Output is correct
6 Correct 118 ms 15164 KB Output is correct
7 Correct 223 ms 20456 KB Output is correct
8 Correct 310 ms 26448 KB Output is correct
9 Correct 533 ms 42208 KB Output is correct
10 Correct 777 ms 55264 KB Output is correct
11 Correct 1705 ms 127072 KB Output is correct
12 Correct 1807 ms 131744 KB Output is correct
13 Execution timed out 2041 ms 131764 KB Time limit exceeded
14 Halted 0 ms 0 KB -