Submission #53113

#	Time	Username	Problem	Language	Result	Execution time	Memory
53113		youngyojun	Popeala (CEOI16_popeala)	C++11	100 / 100	921 ms	24316 KiB

popeala

#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 univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmin(a,b) (a)=min((a),(b))
#define INF (0x3f3f3f3f)
using namespace std;
typedef pair<int, int> pii;

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

vector<pii> G[MAXT];

int dp[MAXK][MAXT];
int mt[MAXN][MAXT];

int AL[MAXN][MAXT];
bool A[MAXN][MAXT];

int S[MAXT];

int N, T, K;

int main() {
	scanf("%d%d%d", &N, &T, &K);
	for(int i = 1; i <= T; i++) {
		scanf("%d", &S[i]);
		S[i] += S[i-1];
	}
	for(int i = 1; i <= N; i++) {
		char str[MAXT];
		scanf(" %s", str+1);
		for(int j = 1; j <= T; j++)
			A[i][j] = '1' == str[j];
	}

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

	fill(dp[0]+1, dp[0]+T+1, INF*2);
	for(int i = 1; i <= K; i++) {
		for(int j = i-1; j <= T; j++)
			for(int x = 0; x <= N; x++)
				mt[x][j] = dp[i-1][j] - S[j]*x;
		for(int x = 0; x <= N; x++)
			for(int j = i; j <= T; j++)
				upmin(mt[x][j], mt[x][j-1]);

		for(int j = i; j <= T; j++) {
			int t = INF*2;
			for(int k = 0; k < sz(G[j]); k++) {
				int s = G[j][k].first, e = k ? G[j][k-1].first-1 : j, x = G[j][k].second;
				s = max(s-1, i-1); e--;
				if(s > e) continue;
				int r = mt[x][e] + S[j]*x;
				if(r < t) t = r;
			}
			dp[i][j] = t;
		}

		printf("%d\n", dp[i][T]);
	}
	return 0;
}

Compilation message (stderr)

popeala.cpp: In function 'int main()':
popeala.cpp:30: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:32:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &S[i]);
   ~~~~~^~~~~~~~~~~~~
popeala.cpp:37:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %s", str+1);
   ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 74 / 74