oj.uz

Submission #632842

# Submission time Handle Problem Language Result Execution time Memory
632842 2022-08-20T22:44:20 Z Cyber_Wolf Popeala (CEOI16_popeala) C++14
100 / 100
 362 ms 18832 KB 
// Problem: P5 - Popeala
// Contest: DMOJ - CEOI '16
// URL: https://dmoj.ca/problem/ceoi16p5
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast")

using namespace std;
using namespace __gnu_pbds;

#define lg long long
#define ordered_set	tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args);
#define endl \n
#define lbound(x, y) lower_bound(x.begin(), x.end(), y) 
#define ubound(x, y) upper_bound(x.begin(), x.end(), y) 
#define sortasc(v) sort(v.begin(), v.end())	
#define sortdesc(v) sort(v.rbegin(), v.rend())	
#define custom_array(a,l, r) int _##a[r-l+1]; int*a=_##a-l;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const lg MOD = 1e9+7, N = 2e5+5, M = 1e7+1, SZ = 1e3+1;
/*
bitset<N> primes;
lg pwrs[N], inv[N];

lg fast_power(lg n, lg k)
{
	if(!k)	return 1;
	if(k&1)	return (fast_power(n, k-1)*n)%MOD;
	lg x = fast_power(n, k/2)%MOD;
	return (x*x)%MOD;
}

void sieve()
{
	primes.set();
	primes[0] = primes[1] = 0;
	for(lg i = 2; i < N; i++)
	{
		if(!primes[i])	continue;
		for(lg j = i*i; j < N; j += i)
		{
			primes[j] = 0;
		}
	}
	return;
}

struct matrix
{
	vector<vector<lg>> con = vector<vector<lg>> (SZ, vector<lg> (SZ));
	matrix operator *(const matrix& a)
	{
		matrix product;
		for(int i = 0; i < (lg)con.size(); i++)
		{
			for(int j = 0; j < (lg)a.con[0].size(); j++)
			{
				for(int k = 0; k < (lg)a.con.size(); k++)
				{
					product.con[i][j] = (product.con[i][j]+(con[i][k]*a.con[k][j])%MOD)%MOD; 
				}
			}
		}
		return product;
	}
};

void preprocess(lg x)
{
	inv[2e5] = fast_power(x, MOD-2);
	for(int i = 2e5-1; i > 1; i--)
	{
		inv[i] = (inv[i+1]*i)%MOD;
	}
	pwrs[0] = 1;
	for(int i = 1; i <= 2e5; i++)
	{
		pwrs[i] = (pwrs[i]*i)%MOD;
	}
	return;
}

*/
lg dp[55][20005];
lg n, t, s;
vector<lg> points(int(2e4+1));
vector<lg> firstUnsolved[20005];

int main()
{
	fastio;
	cin >> n >> t >> s;
	firstUnsolved[0].resize(n+1);
	for(int i = 1; i <= t; i++)	
	{
		cin >> points[i], points[i] += points[i-1];
		firstUnsolved[i].resize(n+1);
	}
	for(int i = 1; i <= n; i++)
	{
		string x;
		cin >> x;
		for(int j = 1; j <= t; j++)
		{
			firstUnsolved[j][i] = (x[j-1] == '0' ? j : firstUnsolved[j-1][i]);
		}
	}
	for(int i = 1; i <= t; i++)
	{
		firstUnsolved[i][0] = i;
		sort(firstUnsolved[i].begin(), firstUnsolved[i].end());
	}
	memset(dp, 0x3f, sizeof(dp));
	dp[0][0] = 0;
	for(int len = 1; len <= s; len++)
	{
		vector<lg> mnm(n+1, 1e18);
		for(int i = 1; i <= t; i++)
		{
			for(int j = 0; j <= n; j++)
			{
				for(int idx = firstUnsolved[i-1][j]; idx < firstUnsolved[i][j]; idx++)
				{
					mnm[j] = min(mnm[j], dp[len-1][idx]-points[idx]*j);
				}
				dp[len][i] = min(dp[len][i], mnm[j]+points[i]*j);
			}
		}
		cout << dp[len][t] << '\n';
	}
	
    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9464 KB Output is correct
2 Correct 5 ms 9504 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 9812 KB Output is correct
2 Correct 13 ms 9812 KB Output is correct
3 Correct 18 ms 9812 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 10452 KB Output is correct
2 Correct 75 ms 10852 KB Output is correct
3 Correct 83 ms 11416 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9464 KB Output is correct
2 Correct 5 ms 9504 KB Output is correct
3 Correct 14 ms 9812 KB Output is correct
4 Correct 13 ms 9812 KB Output is correct
5 Correct 18 ms 9812 KB Output is correct
6 Correct 53 ms 10452 KB Output is correct
7 Correct 75 ms 10852 KB Output is correct
8 Correct 83 ms 11416 KB Output is correct
9 Correct 104 ms 12696 KB Output is correct
10 Correct 166 ms 13396 KB Output is correct
11 Correct 314 ms 18472 KB Output is correct
12 Correct 324 ms 18772 KB Output is correct
13 Correct 352 ms 18764 KB Output is correct
14 Correct 358 ms 18820 KB Output is correct
15 Correct 362 ms 18832 KB Output is correct