oj.uz

Submission #609949

# Submission time Handle Problem Language Result Execution time Memory
609949 2022-07-28T03:29:56 Z chirathnirodha Popeala (CEOI16_popeala) C++17
100 / 100
 375 ms 12724 KB 
//Coded by Chirath Nirodha
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
using namespace std;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define P push
#define I insert
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const string abc="abcdefghijklmnopqrstuvwxyz";
const string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
const ll mod=1e9+7;
const ll inf=1000000000000;
inline void io(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}

void solve(){
    io();
	ll n,t,s;cin>>n>>t>>s;
	ll p[t+1];p[0]=0;
	int last[t+1][n+1];
	memset(last,0,sizeof(last));
	for(int i=1;i<=t;i++){
		cin>>p[i];
		p[i]+=p[i-1];
	}
	for(int i=1;i<=n;i++){
		string str;cin>>str;
		for(int j=0;j<t;j++){
			if(str[j]=='1')last[j+1][i]=last[j][i];
			else last[j+1][i]=j+1;
		}
	}
	for(int i=1;i<=t;i++){
		last[i][0]=i;
		sort(last[i],last[i]+n+1);
	}
	ll dp[t+1][s+1];
	for(int i=0;i<=t;i++)for(int j=0;j<=s;j++)dp[i][j]=inf;
	dp[0][0]=0;
	ll best[n+1];
	for(int i=1;i<=s;i++){
		for(int j=0;j<=n;j++)best[j]=inf;
		for(int j=1;j<=t;j++){
			for(ll k=0;k<=n;k++){
				for(int l=last[j-1][k];l<last[j][k];l++)
					best[k] = min(best[k],dp[l][i-1]-p[l]*k);
				dp[j][i]=min(dp[j][i],best[k]+p[j]*k);
			}
		}
		cout<<dp[t][i]<<endl;
	}
}
int main(){
    io();
	solve();
	//int t;cin>>t;for(int i=0;i<t;i++)solve();
    return 0;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 596 KB Output is correct
2 Correct 11 ms 596 KB Output is correct
3 Correct 11 ms 572 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 1748 KB Output is correct
2 Correct 62 ms 2260 KB Output is correct
3 Correct 69 ms 2892 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 10 ms 596 KB Output is correct
4 Correct 11 ms 596 KB Output is correct
5 Correct 11 ms 572 KB Output is correct
6 Correct 48 ms 1748 KB Output is correct
7 Correct 62 ms 2260 KB Output is correct
8 Correct 69 ms 2892 KB Output is correct
9 Correct 96 ms 4424 KB Output is correct
10 Correct 156 ms 5580 KB Output is correct
11 Correct 289 ms 12508 KB Output is correct
12 Correct 290 ms 12668 KB Output is correct
13 Correct 343 ms 12724 KB Output is correct
14 Correct 375 ms 12592 KB Output is correct
15 Correct 352 ms 12632 KB Output is correct