oj.uz

Submission #52883

# Submission time Handle Problem Language Result Execution time Memory
52883 2018-06-27T06:19:47 Z 윤교준(#1384) Popeala (CEOI16_popeala) C++11
26 / 100
 603 ms 18360 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 = 4005;
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] = min(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) upmin(r, d[s++]); if(~e&1) upmin(r, d[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:47: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:48: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:51: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

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1400 KB Output is correct
2 Correct 6 ms 2732 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 3468 KB Output is correct
2 Correct 72 ms 3576 KB Output is correct
3 Correct 71 ms 3724 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 5300 KB Output is correct
2 Correct 441 ms 6396 KB Output is correct
3 Correct 603 ms 7432 KB Output is correct

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1400 KB Output is correct
2 Correct 6 ms 2732 KB Output is correct
3 Correct 70 ms 3468 KB Output is correct
4 Correct 72 ms 3576 KB Output is correct
5 Correct 71 ms 3724 KB Output is correct
6 Correct 296 ms 5300 KB Output is correct
7 Correct 441 ms 6396 KB Output is correct
8 Correct 603 ms 7432 KB Output is correct
9 Runtime error 68 ms 18360 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Halted 0 ms 0 KB -