oj.uz

Submission #90746

# Submission time Handle Problem Language Result Execution time Memory
90746 2018-12-24T08:23:05 Z IOrtroiii Popeala (CEOI16_popeala) C++17
26 / 100
 2000 ms 131912 KB 
#pragma GCC optimize("O3")
#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:38: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:40:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", a + i);
   ~~~~~^~~~~~~~~~~~~~~
popeala.cpp:44: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 4 ms 2432 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 5832 KB Output is correct
2 Correct 21 ms 5832 KB Output is correct
3 Correct 23 ms 6168 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 15316 KB Output is correct
2 Correct 184 ms 20696 KB Output is correct
3 Correct 302 ms 26600 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 4 ms 2432 KB Output is correct
3 Correct 22 ms 5832 KB Output is correct
4 Correct 21 ms 5832 KB Output is correct
5 Correct 23 ms 6168 KB Output is correct
6 Correct 104 ms 15316 KB Output is correct
7 Correct 184 ms 20696 KB Output is correct
8 Correct 302 ms 26600 KB Output is correct
9 Correct 522 ms 42512 KB Output is correct
10 Correct 832 ms 55552 KB Output is correct
11 Correct 1729 ms 127300 KB Output is correct
12 Correct 1883 ms 131908 KB Output is correct
13 Execution timed out 2001 ms 131912 KB Time limit exceeded
14 Halted 0 ms 0 KB -