oj.uz

Submission #433915

# Submission time Handle Problem Language Result Execution time Memory
433915 2021-06-20T12:11:27 Z rqi Popeala (CEOI16_popeala) C++14
100 / 100
 980 ms 11616 KB 
#include <bits/stdc++.h>
using namespace std;

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

#define mp make_pair
#define f first
#define s second
#define pb push_back
#define bk 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);
}

void ckmin(pair<ll, int>& a, pair<ll, int> 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[20005];
ll ndp[20005];
ll min_dp[20005][55];
ll ans[55];

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 = 1; j <= T; j++){
		solved[0][j] = 1;
	}

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

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


	for(int cur_s = 0; cur_s <= S-1; cur_s++){
		// cout << "cur_s: " << cur_s << "\n";
		for(int i = 0; i <= T; i++){
			ndp[i] = INF;
		}
		for(int i = 0; i <= T; i++){
			for(int j = 0; j <= N; j++){
				min_dp[i][j] = dp[i]-ll(j)*point_sum[i];
				if(i-1 >= 0){
					ckmin(min_dp[i][j], min_dp[i-1][j]);
				}
			}
		}

		vector<pair<pi, int>> bars; //[begin, end], student
		bars.pb(mp(mp(-1, -1), 0)); //careful of transitions including this
		for(int i = 1; i <= N; i++){
			bars.pb(mp(mp(0, -1), i));
		}

		for(int i = 0; i <= T; i++){ //calculate dp[i]
			for(int j = 0; j < sz(bars); j++){
				if(bars[j].f.s >= 0){
					ckmin(ndp[i], min_dp[bars[j].f.s][j]+ll(j)*point_sum[i]);
				}
			}

			// cout << i << " " << ndp[i] << "\n";

			if(i+1 <= T){
				bars.bk.f.s++;
				vector<pair<pi, int>> new_bars;
				vector<pair<pi, int>> to_add;
				for(int bar_ind = 0; bar_ind < sz(bars); bar_ind++){
					int student = bars[bar_ind].s;
					if(solved[student][i+1]){
						new_bars.pb(bars[bar_ind]);
					}
					else{
						new_bars.bk.f.s = bars[bar_ind].f.s;
						to_add.pb(mp(mp(i+1, i), bars[bar_ind].s));
					}
				}
				for(const auto& u: to_add){
					new_bars.pb(u);
				}
				swap(bars, new_bars);
			}
			
		}

		for(int i = 0; i <= T; i++){
			swap(ndp[i], dp[i]);
		}

		ans[cur_s+1] = dp[T];
	}

	//switch for loop order

	for(int j = 1; j <= S; j++){
		cout << ans[j] << "\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 23 ms 716 KB Output is correct
2 Correct 21 ms 792 KB Output is correct
3 Correct 22 ms 716 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 1640 KB Output is correct
2 Correct 143 ms 2052 KB Output is correct
3 Correct 169 ms 2584 KB Output is correct

Subtask #4
74.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 23 ms 716 KB Output is correct
4 Correct 21 ms 792 KB Output is correct
5 Correct 22 ms 716 KB Output is correct
6 Correct 116 ms 1640 KB Output is correct
7 Correct 143 ms 2052 KB Output is correct
8 Correct 169 ms 2584 KB Output is correct
9 Correct 302 ms 3852 KB Output is correct
10 Correct 378 ms 5452 KB Output is correct
11 Correct 880 ms 11588 KB Output is correct
12 Correct 960 ms 11600 KB Output is correct
13 Correct 980 ms 11596 KB Output is correct
14 Correct 944 ms 11616 KB Output is correct
15 Correct 953 ms 11604 KB Output is correct