oj.uz

답안 #257746

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
257746 2020-08-04T17:04:26 Z amiratou 조교 (CEOI16_popeala) C++14
100 / 100
 1673 ms 50692 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define rando mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define fi first
#define se second
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define debugii(x) cerr << " - " << #x << ": " << x.fi<<","<<x.se << endl;
#define sep() cerr << "--------------------" << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ld long double
#define ll long long
//#define int ll
#define ii pair<int,int>
#define v vector<int>
#define vii vector<ii>
#define vv vector<vector<int> >
#define mp make_pair
#define pb push_back
#define EPS 1e-9
const int INF = 2000000009;
const int MOD = 1000000007; // 998244353
const int MX_t = 20003 , MX_n = 53;
int n,t,s,p[MX_t],A[MX_t][MX_n],dp[MX_n][MX_t],pre[MX_n][MX_t],par[MX_t];
string S;
vii ranges[MX_n][MX_t];
int find_set(int i){
	if(par[i]==i)return i;
	return par[i]=find_set(par[i]);
}
int32_t main(){
	boost;
	//freopen(".in","r",stdin);
	cin>>n>>t>>s;
	for (int i = 1; i <= t; ++i)
	{
		cin>>p[i];
		if(i)p[i]+=p[i-1];
	}
	for (int i = 0; i < n; ++i)
	{
		cin>>S;
		for (int j = 1; j <= t; ++j)
		{
			if(S[j-1]=='0')A[j][i]=j;
			else A[j][i]=A[j-1][i];
		}
	}
	for (int i = 1; i <= t; ++i)
	{
		A[i][n]=i;
		sort(A[i],A[i]+n+1);
	}
	for (int i = 0; i < MX_n; ++i)
		for (int j = 0; j <= t; ++j)
			dp[i][j]=INF,pre[i][j]=INF;
	dp[0][0]=0;
	for (int j = 1; j <= t; ++j)
	{
		if(A[j][0])ranges[0][A[j][0]].pb({1,j});
		for (int i = 0; i <= n; ++i)
			if((A[j][i]+1) <= A[j][i+1])
				ranges[i+1][A[j][i+1]].pb({A[j][i]+1,j});
	}
	for (int k = 1; k <= s; ++k)
	{
		for (int x = 0; x <= n; ++x)
		{
			stack<int> st;
			for (int j = 1; j <= t; ++j)
				par[j]=j;
			for (int j = 1; j <= t; ++j)
			{
				int val;
				if(dp[k-1][j-1]!=INF)val=dp[k-1][j-1]-p[j-1]*x;
				else val=INF;
				while(!st.empty() && ((dp[k-1][st.top()-1]==INF)?INF:(dp[k-1][st.top()-1]-p[st.top()-1]*x)) > val){
					par[st.top()]=j;
					st.pop();
				}
				st.push(j);
				for(auto it:ranges[x][j]){
					int h=find_set(it.fi);
					if(dp[k-1][h-1]!=INF)pre[x][it.se]=dp[k-1][h-1]-p[h-1]*x;
					else pre[x][it.se]=INF;
				}
			}
		}
		for (int j = 1; j <= t; ++j)
			for (int x = 0; x <= n; ++x)
				if(pre[x][j]!=INF)dp[k][j]=min(dp[k][j],pre[x][j]+p[j]*x);
		cout<<dp[k][t]<<"\n";
	}
	return 0;
}

//do smth instead of nothing and stay organized
//long long
//array bounds
//special cases
//binary search

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 25728 KB Output is correct
2 Correct 19 ms 25856 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 26368 KB Output is correct
2 Correct 49 ms 26360 KB Output is correct
3 Correct 50 ms 26368 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 163 ms 28664 KB Output is correct
2 Correct 230 ms 29816 KB Output is correct
3 Correct 304 ms 30968 KB Output is correct

Subtask #4
74.0 / 74.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 25728 KB Output is correct
2 Correct 19 ms 25856 KB Output is correct
3 Correct 51 ms 26368 KB Output is correct
4 Correct 49 ms 26360 KB Output is correct
5 Correct 50 ms 26368 KB Output is correct
6 Correct 163 ms 28664 KB Output is correct
7 Correct 230 ms 29816 KB Output is correct
8 Correct 304 ms 30968 KB Output is correct
9 Correct 492 ms 33656 KB Output is correct
10 Correct 753 ms 36728 KB Output is correct
11 Correct 1379 ms 50168 KB Output is correct
12 Correct 1409 ms 50692 KB Output is correct
13 Correct 1640 ms 50612 KB Output is correct
14 Correct 1673 ms 50552 KB Output is correct
15 Correct 1663 ms 50612 KB Output is correct