Submission #90745

#	Time	Username	Problem	Language	Result	Execution time	Memory
90745		IOrtroiii	Popeala (CEOI16_popeala)	C++14	26 / 100	2041 ms	131764 KiB

popeala

#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 (stderr)

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 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 0 / 74