oj.uz

Submission #52888

# Submission time Handle Problem Language Result Execution time Memory
52888 2018-06-27T06:33:46 Z 윤교준(#1384) Popeala (CEOI16_popeala) C++11
9 / 100
 2000 ms 85736 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 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];

	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];
vector<pii> VG[MAXT];

int mp[MAXT][MAXK];

int 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);

/*
		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 i = 1; i <= T; i++) {
		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, 0); e--;
			if(s > e) continue;
			for(int j = s; j <= e; j++) {
				VG[j].eb(i, c);
			}
		}
	}

	for(int j = 1; j <= K; j++) {
		for(int i = 0; i <= T; i++)
			for(int k = 0; k <= K; k++)
				mp[i][k] = INF*2;
		for(int i = 0; i <= T; i++) {
			for(pii v : VG[i]) {
				int t = dp[j-1][i] - S[i] * v.second;
				if(t < mp[v.first][v.second])
					mp[v.first][v.second] = t;
			}
		}

		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 = mp[i][c] + S[i] * c;
				if(ret < t) t = ret;
			}
			dp[j][i] = t;
		}
	}

/*
	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:59: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 5624 KB Output is correct
2 Incorrect 7 ms 5988 KB Output isn't correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 7852 KB Output is correct
2 Correct 31 ms 7852 KB Output is correct
3 Correct 30 ms 8012 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 513 ms 32712 KB Output is correct
2 Correct 1091 ms 53788 KB Output is correct
3 Execution timed out 2074 ms 85736 KB Time limit exceeded

Subtask #4
0 / 74.0

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