Submission #433915

#	Time	Username	Problem	Language	Result	Execution time	Memory
433915		rqi	Popeala (CEOI16_popeala)	C++14	100 / 100	980 ms	11616 KiB

popeala

#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 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 74 / 74