oj.uz

Submission #749519

# Submission time Handle Problem Language Result Execution time Memory
749519 2023-05-28T06:48:15 Z 박상훈(#9965) Popeala (CEOI16_popeala) C++17
8 / 100
 2000 ms 1568 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], n, t, s;
char b[55][20020], bS[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
8.0 / 8.0

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

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 428 ms 1564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2060 ms 1568 KB Time limit exceeded
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 Correct 2 ms 724 KB Output is correct
3 Incorrect 428 ms 1564 KB Output isn't correct
4 Halted 0 ms 0 KB -