oj.uz

Submission #90747

# Submission time Handle Problem Language Result Execution time Memory
90747 2018-12-24T08:23:39 Z IOrtroiii Popeala (CEOI16_popeala) C++14
100 / 100
 1988 ms 132120 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#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:37: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:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", a + i);
   ~~~~~^~~~~~~~~~~~~~~
popeala.cpp:43: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 2292 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 5848 KB Output is correct
2 Correct 19 ms 5848 KB Output is correct
3 Correct 22 ms 5848 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 15100 KB Output is correct
2 Correct 202 ms 20468 KB Output is correct
3 Correct 282 ms 26332 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 888 KB Output is correct
2 Correct 3 ms 2292 KB Output is correct
3 Correct 20 ms 5848 KB Output is correct
4 Correct 19 ms 5848 KB Output is correct
5 Correct 22 ms 5848 KB Output is correct
6 Correct 96 ms 15100 KB Output is correct
7 Correct 202 ms 20468 KB Output is correct
8 Correct 282 ms 26332 KB Output is correct
9 Correct 463 ms 42248 KB Output is correct
10 Correct 788 ms 55220 KB Output is correct
11 Correct 1709 ms 127028 KB Output is correct
12 Correct 1874 ms 131680 KB Output is correct
13 Correct 1933 ms 131680 KB Output is correct
14 Correct 1907 ms 132064 KB Output is correct
15 Correct 1988 ms 132120 KB Output is correct