oj.uz

답안 #52913

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
52913 2018-06-27T07:18:04 Z 윤교준(#1384) 조교 (CEOI16_popeala) C++11
26 / 100
 2000 ms 34320 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 {
	int d[MX*2];
	int 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) {
		int 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];

int BL[MAXN][MAXT];
bool B[MAXN][MAXT];

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 i = 1; i <= K; i++)
		printf("%u\n", dp[i][T]);
	return 0;
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:64: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
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5240 KB Output is correct
2 Correct 8 ms 6628 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 8108 KB Output is correct
2 Correct 70 ms 8108 KB Output is correct
3 Correct 70 ms 8108 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 339 ms 10288 KB Output is correct
2 Correct 426 ms 11888 KB Output is correct
3 Correct 611 ms 13060 KB Output is correct

Subtask #4
0 / 74.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5240 KB Output is correct
2 Correct 8 ms 6628 KB Output is correct
3 Correct 71 ms 8108 KB Output is correct
4 Correct 70 ms 8108 KB Output is correct
5 Correct 70 ms 8108 KB Output is correct
6 Correct 339 ms 10288 KB Output is correct
7 Correct 426 ms 11888 KB Output is correct
8 Correct 611 ms 13060 KB Output is correct
9 Correct 1027 ms 16900 KB Output is correct
10 Correct 1341 ms 19708 KB Output is correct
11 Execution timed out 2047 ms 34320 KB Time limit exceeded
12 Halted 0 ms 0 KB -