oj.uz

Submission #749547

# Submission time Handle Problem Language Result Execution time Memory
749547 2023-05-28T07:47:21 Z 박상훈(#9965) Popeala (CEOI16_popeala) C++17
100 / 100
 487 ms 18652 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;
typedef long long ll;
constexpr int INF = 1e18;
int dp[55][20020], opt[55][20020], a[20020], aS[20020], bS[55][20020], n, t, s;
char b[55][20020];
ll bt[20020];

int L[55], R[55];
ll val[55], cur[55];

int f(int l, int r){
	int ret = 0;
	for (int i=1;i<=n;i++){
		if (bS[i][r] - bS[i][l-1] == r-l+1) ret += aS[r] - aS[l-1];
	}
	return ret;
}

signed main(){
	scanf("%lld %lld %lld", &n, &t, &s);
	for (int i=1;i<=t;i++){
		scanf("%lld", a+i);
		aS[i] = aS[i-1] + a[i];
	} 
	for (int i=1;i<=n;i++){
		scanf("%s", b[i]+1);
		for (int j=1;j<=t;j++){
			bS[i][j] = bS[i][j-1] + (b[i][j]=='1');
		}
	} 

	for (int i=1;i<=t;i++){
		for (int j=1;j<=n;j++) if (b[j][i]=='1') bt[i] |= 1LL<<j;
	}
	for (int i=1;i<=n;i++) bt[0] |= 1LL<<i;

	fill(dp[0]+1, dp[0]+t+1, INF);
	dp[0][0] = 0;
	
	for (int z=1;z<=s;z++){
		for (int c=0;c<=n;c++){
			L[c] = 1e9 + 100;
			R[c] = -1;
			val[c] = INF;
			cur[c] = 0;
		}

		for (int i=0;i<=t;i++){
			dp[z][i] = INF;
			
			for (int c=0;c<=n;c++) if (L[c] <= R[c]) {
				ll nxt = cur[c] & bt[i];
				if (nxt==cur[c]) continue;
				int idx = __builtin_popcountll(nxt);
				
				cur[idx] = nxt;
				L[idx] = min(L[idx], L[c]);
				R[idx] = max(R[idx], R[c]);

				for (int j=L[c];j<=R[c];j++) val[idx] = min(val[idx], dp[z-1][j] - aS[j] * idx);

				L[c] = 1e9 + 100;
				R[c] = -1;
				val[c] = INF;
				cur[c] = 0;
			}

			for (int c=0;c<=n;c++) if (L[c] <= R[c]) dp[z][i] = min(dp[z][i], val[c] + aS[i] * c);

			cur[n] = bt[0];
			L[n] = min(L[n], i);
			R[n] = max(R[n], i);
			val[n] = min(val[n], dp[z-1][i] - aS[i] * n);

		}

		printf("%lld\n", dp[z][t]);
		

		// dp[z][0] = INF;
		// for (int i=1;i<=t;i++){
		// 	dp[z][i] = INF;
		// 	for (int j=0;j<i;j++){
		// 		ll val = (ll)dp[z-1][j] + f(j+1, i);
		// 		if (dp[z][i] > val){
		// 			dp[z][i] = val;
		// 			opt[z][i] = j;
		// 		}
		// 	}
		// }

		// cout << dp[z][t] << '\n';
		// for (int i=1;i<=t;i++) printf("%lld ", dp[z][i]);
		// printf("\n");
		// for (int i=1;i<=t;i++) printf("%lld ", opt[z][i]);
		// printf("\n");
		// for (int i=1;i<t;i++) assert(opt[z][i] <= opt[z][i+1]);
	}
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |  scanf("%lld %lld %lld", &n, &t, &s);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
popeala.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |   scanf("%lld", a+i);
      |   ~~~~~^~~~~~~~~~~~~
popeala.cpp:29:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |   scanf("%s", b[i]+1);
      |   ~~~~~^~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 596 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1340 KB Output is correct
2 Correct 14 ms 1276 KB Output is correct
3 Correct 15 ms 1348 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 2692 KB Output is correct
2 Correct 103 ms 3632 KB Output is correct
3 Correct 103 ms 4572 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 15 ms 1340 KB Output is correct
4 Correct 14 ms 1276 KB Output is correct
5 Correct 15 ms 1348 KB Output is correct
6 Correct 73 ms 2692 KB Output is correct
7 Correct 103 ms 3632 KB Output is correct
8 Correct 103 ms 4572 KB Output is correct
9 Correct 130 ms 6776 KB Output is correct
10 Correct 224 ms 8656 KB Output is correct
11 Correct 372 ms 18204 KB Output is correct
12 Correct 379 ms 18636 KB Output is correct
13 Correct 480 ms 18652 KB Output is correct
14 Correct 470 ms 18568 KB Output is correct
15 Correct 487 ms 18648 KB Output is correct