oj.uz

Submission #240625

# Submission time Handle Problem Language Result Execution time Memory
240625 2020-06-20T09:59:37 Z alishahali1382 Popeala (CEOI16_popeala) C++14
17 / 100
 2000 ms 5944 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int MAXN=20010, K=51;

int n, m, k, u, v, x, y, t, a, b, ans;
int A[MAXN];
int dp[K][MAXN];
int seg[MAXN<<2], lazy[MAXN<<2];
string S[K];
int last0[K][MAXN];

void add_lazy(int id, int val){
	lazy[id]+=val;
	seg[id]+=val;
}
void shift(int id){
	if (!lazy[id]) return ;
	add_lazy(id<<1, lazy[id]);
	add_lazy(id<<1 | 1, lazy[id]);
	lazy[id]=0;
}
void Add(int id, int tl, int tr, int l, int r, int val){
	if (r<=tl || tr<=l) return ;
	if (l<=tl && tr<=r){
		add_lazy(id, val);
		return ;
	}
	shift(id);
	int mid=(tl+tr)>>1;
	Add(id<<1, tl, mid, l, r, val);
	Add(id<<1 | 1, mid, tr, l, r, val);
	seg[id]=min(seg[id<<1], seg[id<<1 | 1]);
}
int Get(int id, int tl, int tr, int l, int r){
	if (r<=tl || tr<=l) return seg[0];
	if (l<=tl && tr<=r) return seg[id];
	shift(id);
	int mid=(tl+tr)>>1;
	return min(Get(id<<1, tl, mid, l, r), Get(id<<1 | 1, mid, tr, l, r));
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>m>>n>>k;
	for (int i=1; i<=n; i++) cin>>A[i];
	for (int i=1; i<=m; i++){
		cin>>S[i];
		S[i]="#"+S[i];
		for (int j=1; j<=n; j++){
			last0[i][j]=last0[i][j-1];
			if (S[i][j]=='0') last0[i][j]=j;
		}
	}
	memset(dp, 31, sizeof(dp));
	dp[0][0]=0;
	for (int j=1; j<=k; j++){
		memset(seg, 0, sizeof(seg));
		memset(lazy, 0, sizeof(lazy));
		seg[0]=inf;
		Add(1, 0, n, 0, 1, dp[j-1][0]);
		int shit=0;
		for (int i=1; i<=n; i++){
			for (int x=1; x<=m; x++){
				if (S[x][i]=='1') Add(1, 0, n, last0[x][i], i, +A[i]);
				else{
					for (int y=last0[x][i-1]+1; y<i; y++, shit++)
						Add(1, 0, n, last0[x][y], y, -A[y]);
				}
				assert(shit<=n*m);
			}
			Add(1, 0, n, i, i+1, dp[j-1][i]);
			dp[j][i]=Get(1, 0, n, j-1, i);
		}
		cout<<dp[j][n]<<'\n';
	}
	return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 10 ms 5248 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 364 ms 5376 KB Output is correct
2 Correct 335 ms 5328 KB Output is correct
3 Correct 346 ms 5376 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1757 ms 5944 KB Output is correct
2 Execution timed out 2085 ms 5888 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 10 ms 5248 KB Output is correct
3 Correct 364 ms 5376 KB Output is correct
4 Correct 335 ms 5328 KB Output is correct
5 Correct 346 ms 5376 KB Output is correct
6 Correct 1757 ms 5944 KB Output is correct
7 Execution timed out 2085 ms 5888 KB Time limit exceeded
8 Halted 0 ms 0 KB -