oj.uz

Submission #240575

# Submission time Handle Problem Language Result Execution time Memory
240575 2020-06-20T06:24:46 Z Goolakh Popeala (CEOI16_popeala) C++17
100 / 100
 371 ms 20472 KB 
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O2,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Os")

#define F first
#define S second
#define pb push_back
#define SZ(x) (ll)(x.size())
#define all(x) x.begin(),x.end()
//#define mp make_pair

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn=50+10, maxm=2e4+10, lg=22, mod=1e9+9, inf=1e18;

ll n,t,s;
ll a[maxm],pre[maxm][maxn],dp[maxn][maxm],mnn[maxn][maxn];

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	cin>>n>>t>>s;
	for(int i=1;i<=t;i++) cin>>a[i], a[i]+=a[i-1];
	for(int i=1;i<=n;i++){
		string s; cin>>s;
		for(int j=1;j<=t;j++) pre[j][i]=(s[j-1]=='0' ? j:pre[j-1][i]);
	}
	for(int i=1;i<=t;i++) pre[i][n+1]=i, sort(pre[i]+1,pre[i]+n+1);
	memset(dp,69,sizeof(dp)), memset(mnn,69,sizeof(mnn));
	dp[0][0]=0;
	for(int i=1;i<=s;cout<<dp[i++][t]<<endl)for(int j=1;j<=t;j++)for(int k=0;k<=n;k++){
		for(int l=pre[j-1][k+1];l<pre[j][k+1];l++) mnn[k][i]=min(mnn[k][i],dp[i-1][l]-a[l]*k);
		if(pre[j][k+1]) dp[i][j]=min(dp[i][j],mnn[k][i]+a[j]*k);
	}
	
	return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9728 KB Output is correct
2 Correct 9 ms 9728 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 9984 KB Output is correct
2 Correct 23 ms 9984 KB Output is correct
3 Correct 19 ms 10112 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 10880 KB Output is correct
2 Correct 70 ms 11392 KB Output is correct
3 Correct 81 ms 11904 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9728 KB Output is correct
2 Correct 9 ms 9728 KB Output is correct
3 Correct 19 ms 9984 KB Output is correct
4 Correct 23 ms 9984 KB Output is correct
5 Correct 19 ms 10112 KB Output is correct
6 Correct 53 ms 10880 KB Output is correct
7 Correct 70 ms 11392 KB Output is correct
8 Correct 81 ms 11904 KB Output is correct
9 Correct 109 ms 13184 KB Output is correct
10 Correct 166 ms 14336 KB Output is correct
11 Correct 280 ms 20344 KB Output is correct
12 Correct 301 ms 20472 KB Output is correct
13 Correct 371 ms 20472 KB Output is correct
14 Correct 351 ms 20472 KB Output is correct
15 Correct 349 ms 20472 KB Output is correct