oj.uz

Submission #433778

# Submission time Handle Problem Language Result Execution time Memory
433778 2021-06-20T10:42:04 Z rqi Popeala (CEOI16_popeala) C++14
26 / 100
 2000 ms 4044 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;

#define mp make_pair
#define f first
#define s second
#define pb push_back

#define sz(x) (int)(x).size()

void ckmax(int& a, int b){
	a = max(a, b);
}

void ckmin(ll& a, ll b){
	a = min(a, b);
}

const ll INF = 1e18;

int N, T, S;

int points[20005];
ll point_sum[20005];
bool solved[55][20005];
ll dp[55][20005];

int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> N >> T >> S;
	for(int i = 1; i <= T; i++){
		cin >> points[i];
	}
	for(int i = 1; i <= N; i++){
		string s;
		cin >> s;
		for(int j = 1; j <= T; j++){
			if(s[j-1] == '1'){
				solved[i][j] = 1;
			}
		}
	}

	for(int j = 0; j <= S; j++){
		for(int i = 0; i <= T; i++){
			dp[j][i] = INF;
		}
	}

	for(int i = 1; i <= T; i++){
		point_sum[i] = point_sum[i-1]+points[i];
	}

	dp[0][0] = 0;

	for(int i = 1; i <= T; i++){
		bitset<55> bad;


		for(int j = i-1; j >= 0; j--){
			ll cur_points = 0;
			for(int k = 1; k <= N; k++){
				if(!solved[k][j+1]){
					bad[k] = 1;
				}

				if(!bad[k]){
					cur_points+=point_sum[i]-point_sum[j];
				}
			}

			for(int k = 1; k <= S; k++){
				ckmin(dp[k][i], dp[k-1][j]+cur_points);
			}
		}
	}

	//switch for loop order

	// for(int i = 0; i <= T; i++){
	// 	for(int j = 0; j <= S; j++){
	// 		cout << i << " " << j << " " << dp[j][i] << "\n";
	// 	}
	// }

	for(int j = 1; j <= S; j++){
		cout << dp[j][T] << "\n";
	}

}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 972 KB Output is correct
2 Correct 27 ms 984 KB Output is correct
3 Correct 24 ms 980 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 461 ms 1868 KB Output is correct
2 Correct 879 ms 2276 KB Output is correct
3 Correct 1549 ms 2784 KB Output is correct

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 26 ms 972 KB Output is correct
4 Correct 27 ms 984 KB Output is correct
5 Correct 24 ms 980 KB Output is correct
6 Correct 461 ms 1868 KB Output is correct
7 Correct 879 ms 2276 KB Output is correct
8 Correct 1549 ms 2784 KB Output is correct
9 Execution timed out 2073 ms 4044 KB Time limit exceeded
10 Halted 0 ms 0 KB -