oj.uz

Submission #749521

# Submission time Handle Problem Language Result Execution time Memory
749521 2023-05-28T06:53:53 Z 박상훈(#9965) Popeala (CEOI16_popeala) C++17
0 / 100
 369 ms 3520 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];

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');
		}
	} 

	fill(dp[0]+1, dp[0]+t+1, INF);
	dp[0][0] = 0;
	
	for (int z=1;z<=s;z++){
		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++) assert(opt[z][i] <= opt[z][i+1]);
	}
}

Compilation message

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

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Runtime error 4 ms 1108 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 1900 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 369 ms 3520 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Runtime error 4 ms 1108 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -