oj.uz

Submission #52906

# Submission time Handle Problem Language Result Execution time Memory
52906 2018-06-27T07:13:14 Z 윤교준(#1384) Popeala (CEOI16_popeala) C++11
0 / 100
 325 ms 10220 KB 
#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define upmin(a,b) (a)=min((a),(b))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef unsigned int ui;
typedef long long ll;
typedef pair<int, int> pii;
static unsigned char str[55000055], *p=str;

const int MAXT = 20005;
const int MAXN = 55;
const int MAXK = 55;
const int MX = 32768;

struct SEG {
	ui d[MX*2];
	ui A[MX];

	void upd(int x, int r) {
		A[x] = r; x += MX; d[x] = r;
		for(x /= 2; x; x /= 2)
			d[x] = d[x*2] < d[x*2+1] ? d[x*2] : d[x*2+1];
	}
	int get(int s, int e) {
		ui r = INF*2;
		if(e-s < 20) {
			for(int i = s; i <= e; i++)
				if(A[i] < r) r = A[i];
			return r;
		}
		for(s += MX, e += MX; s <= e; s /= 2, e /= 2) {
			if(s&1) {
				if(d[s] < r) r = d[s];
				s++;
			}
			if(~e&1) {
				if(d[e] < r) r = d[e];
				e--;
			}
		}
		return r;
	}
} seg[MAXN];

vector<pii> VC[MAXT];

ui dp[MAXK][MAXT];

ui BL[MAXN][MAXT];
bitset<MAXT> B[MAXN];

int S[MAXT];
int A[MAXT];

int N, T, K;

int main() {
	fread(str, 1, 55000055, stdin);
	rf(N) rf(T) rf(K)
	for(int i = 1; i <= T; i++) { rf(A[i]) }
	for(int i = 1; i <= N; i++) {
		for(int j = 1; j <= T; j++) {
			while(*p<48)p++;
			B[i][j] = (bool)(*p++ == '1');
		}
	}

	for(int i = 1; i <= T; i++)
		S[i] = S[i-1] + A[i];
	
	for(int i = 1; i <= N; i++) {
		for(int j = 1; j <= T; j++) {
			if(!B[i][j]) continue;
			BL[i][j] = B[i][j-1] ? BL[i][j-1] : j;
		}
	}

	for(int i = 1; i <= T; i++) {
		vector<int> V;
		for(int j = 1; j <= N; j++)
			if(BL[j][i]) V.pb(BL[j][i]);
		sorv(V);
		for(; !V.empty();) {
			int c = V.back(), n = sz(V);
			for(; !V.empty() && V.back() == c; V.pop_back());
			VC[i].eb(c, n);
		}
		VC[i].eb(1, 0);
	}

	for(int i = 0; i < MAXK; i++)
		fill(dp[i], dp[i]+MAXT, INF*2);
	dp[0][0] = 0;

	for(int j = 1; j <= K; j++) {
		for(int c = 0; c <= N; c++) {
			for(int i = j-1; i <= T; i++) {
				seg[c].upd(i, dp[j-1][i] - S[i]*c);
			}
		}
		for(int i = j; i <= T; i++) {
			ui t = INF*2;
			for(int k = 0; k < sz(VC[i]); k++) {
				int s = VC[i][k].first, e = k ? VC[i][k-1].first-1 : i, c = VC[i][k].second;
				s = max(s-1, j-1); e--;
				if(s > e) continue;
				ui ret = seg[c].get(s, e) + S[i] * c;
				if(ret < t) t = ret;
			}
			dp[j][i] = t;
		}
	}

/*
	for(int j = 1; j <= K; j++) {
		for(int i = 1; i <= T; i++)
			printf("%d ", dp[j][i]);
		puts("");
	}
*/

	for(int i = 1; i <= K; i++)
		printf("%u\n", dp[i][T]);
	return 0;
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:65:7: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  fread(str, 1, 55000055, stdin);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5332 KB Output is correct
2 Incorrect 9 ms 6736 KB Output isn't correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 81 ms 8096 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 325 ms 10220 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5332 KB Output is correct
2 Incorrect 9 ms 6736 KB Output isn't correct