oj.uz

Submission #30662

# Submission time Handle Problem Language Result Execution time Memory
30662 2017-07-26T03:08:06 Z zscoder Popeala (CEOI16_popeala) C++14
0 / 100
 179 ms 15440 KB 
#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<=t;i++) dp[0][i]=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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 15440 KB Output is correct
2 Incorrect 0 ms 15440 KB Output isn't correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 15440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 179 ms 15440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 15440 KB Output is correct
2 Incorrect 0 ms 15440 KB Output isn't correct