oj.uz

답안 #749542

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
749542 2023-05-28T07:35:30 Z 박상훈(#9965) 조교 (CEOI16_popeala) C++17
0 / 100
 96 ms 2840 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];
list<array<ll, 3>> dq[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++) dq[c].clear();

		for (int i=0;i<=t;i++){
			dp[z][i] = INF;

			for (int c=1;c<=n;c++) if (!dq[c].empty()){
				while(!dq[c].empty() && (dq[c].front()[2] & bt[i]) != dq[c].front()[2]){
					auto p = dq[c].front(); dq[c].pop_front();
					p[2] &= bt[i];

					int idx = __builtin_popcountll(p[2]);
					p[1] += idx * p[0] - c * p[0];

					while(!dq[idx].empty() && dq[idx].back()[1] >= p[1]) dq[idx].pop_back();
					dq[idx].push_back(p);
				}
			}

			for (int c=0;c<=n;c++) if (!dq[c].empty()) dp[z][i] = min(dp[z][i], dq[c].front()[1] + aS[i] * c);

			// printf("\ni = %lld\n", i);
			// for (int i=0;i<=n;i++){
			// 	for (auto &[x, y, z]:dq[i]) printf("(%lld, %lld, %lld) ", x, y, z);
			// 	printf("\n");
			// }
			// printf("-> %lld\n", dp[z][i]);

			int idx = __builtin_popcountll(bt[0]);
			array<ll, 3> p = {-aS[i], dp[z-1][i] - aS[i] * idx, bt[0]};
			
			while(!dq[idx].empty() && dq[idx].back()[1] >= p[1]) dq[idx].pop_back();
			dq[idx].push_back(p);


			
		}

		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:21:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |  scanf("%lld %lld %lld", &n, &t, &s);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
popeala.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |   scanf("%lld", a+i);
      |   ~~~~~^~~~~~~~~~~~~
popeala.cpp:27:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |   scanf("%s", b[i]+1);
      |   ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 692 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 1356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 96 ms 2840 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 692 KB Output isn't correct
3 Halted 0 ms 0 KB -