oj.uz

답안 #52885

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
52885 2018-06-27T06:21:16 Z 윤교준(#1384) 조교 (CEOI16_popeala) C++11
26 / 100
 2000 ms 29268 KB 
#include <bits/stdc++.h>
#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 long long ll;
typedef pair<int, int> pii;

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

struct SEG {
	int d[MX*2];

	void upd(int x, int 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; 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];

int dp[MAXK][MAXT];

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

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

int N, T, K;

int main() {
	scanf("%d%d%d", &N, &T, &K);
	for(int i = 1; i <= T; i++) scanf("%d", &A[i]);
	for(int i = 1; i <= N; i++) {
		for(int j = 1; j <= T; j++) {
			char c; scanf(" %c", &c);
			B[i][j] = (bool)(c == '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);

/*
		printf("VC %d : ", i);
		for(pii v : VC[i]) printf("(%d,%d) ", v.first, v.second);
		puts("");
*/
	}

	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 = 0; i <= T; i++) {
				seg[c].upd(i, dp[j-1][i] - S[i]*c);
			}
		}
		for(int i = j; i <= T; i++) {
			int 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;
				int ret = seg[c].get(s, e) + S[i] * c;
				//printf("j=%d, i=%d : c=%d, s=%d, e=%d :: %d\n", j, i, c, s, e, ret);
				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("%d\n", dp[i][T]);
	return 0;
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &T, &K);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
popeala.cpp:55:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= T; i++) scanf("%d", &A[i]);
                              ~~~~~^~~~~~~~~~~~~
popeala.cpp:58:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    char c; scanf(" %c", &c);
            ~~~~~^~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 7648 KB Output is correct
2 Correct 112 ms 7648 KB Output is correct
3 Correct 77 ms 7700 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 310 ms 9728 KB Output is correct
2 Correct 443 ms 10880 KB Output is correct
3 Correct 620 ms 11960 KB Output is correct

Subtask #4
0 / 74.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5240 KB Output is correct
2 Correct 9 ms 6592 KB Output is correct
3 Correct 74 ms 7648 KB Output is correct
4 Correct 112 ms 7648 KB Output is correct
5 Correct 77 ms 7700 KB Output is correct
6 Correct 310 ms 9728 KB Output is correct
7 Correct 443 ms 10880 KB Output is correct
8 Correct 620 ms 11960 KB Output is correct
9 Correct 1048 ms 15052 KB Output is correct
10 Correct 1472 ms 17284 KB Output is correct
11 Execution timed out 2058 ms 29268 KB Time limit exceeded
12 Halted 0 ms 0 KB -