Submission #30656

#	Time	Username	Problem	Language	Result	Execution time	Memory
30656		zscoder	Popeala (CEOI16_popeala)	C++14	0 / 100	26 ms	15440 KiB

popeala

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<int,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<ll>::iterator sit;
typedef map<ll,ll>::iterator mit;

ll a[20001];
ll pref[20001];
const ll INF = ll(1e18);
bool solve[51][20001];
ll dp[51][20001];
int cnt[51][20001];
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n,t,k; cin>>n>>t>>k;
	for(int i=1;i<=t;i++) 
	{
		cin>>a[i];
		pref[i]=pref[i-1]+a[i];
	}
	for(int i=0;i<n;i++)
	{
		string s; cin>>s;
		for(int j=1;j<=t;j++)
		{
			solve[i][j]=s[j-1]-'0';
			cnt[i][j]=cnt[i][j-1];
			if(!solve[i][j])
			{
				cnt[i][j]++;
			}
		}
	}
	dp[0][0]=0;
	for(int i=1;i<=k;i++) dp[i][0]=INF;
	for(int i = 1; i <= k; i++)
	{
		int opt = 0;
		for(int j = 1; j <= t; j++)
		{
			dp[i][j]=INF;
			for(int k = opt; k < j; k++)
			{
				ll sc=0;
				for(int l = 0; l < n; l++)
				{
					if(cnt[l][j]==cnt[l][k])
					{
						sc+=pref[j]-pref[k];
					}
				}
				if(sc+dp[i-1][k]<dp[i][j])
				{
					dp[i][j]=sc+dp[i-1][k];
					opt=k;
				}
			}
		}
	}
	for(int i=1;i<=k;i++)
	{
		cout<<dp[i][t]<<'\n';
	}
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 74