oj.uz

Submission #537036

# Submission time Handle Problem Language Result Execution time Memory
537036 2022-03-14T09:55:05 Z jamezzz Popeala (CEOI16_popeala) C++17
100 / 100
 1994 ms 71660 KB 
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#define fi first
#define se second
#define sf scanf
#define pf printf
#define INF 1023456789
typedef pair<int,int> ii;

int t,n,s,p[20005],r[55][20005],pfx[200005];
ii pv[20005][55];
int dp[55][20005],st[55][20][20005];
char ch[20005];

inline int rd() {
    int x = 0;
    char ch = getchar_unlocked();
    while (ch < '0' || ch > '9') ch = getchar_unlocked();
    while (ch >= '0' && ch <= '9'){
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar_unlocked();
	}
    return x;
}
//change getchar_unlocked() to getchar() for testing

int main(){
	n=rd();t=rd();s=rd();
	for(int i=1;i<=t;++i){
		p[i]=rd();
		pfx[i]=p[i]+pfx[i-1];
	}
	for(int i=0;i<n;++i){
		for(int j=1;j<=t;++j){
			char ch = getchar_unlocked();
			while (ch < '0' || ch > '9') ch = getchar_unlocked();
			r[i][j]=ch-'0'+r[i][j-1];
		}
	}
	for(int i=1;i<=t;++i){
		for(int j=0;j<=n;++j){
			//find range with exactly j all 1s
			int lo=1,hi=i,mid,res=-1,res2=-1;
			while(lo<=hi){
				mid=(lo+hi)/2;
				int cnt=0;
				for(int k=0;k<n;++k){
					if(r[k][i]-r[k][mid-1]==i-mid+1)++cnt;
				}
				if(cnt>=j)res=mid,hi=mid-1;
				else lo=mid+1;
			}
			lo=1,hi=i;
			while(lo<=hi){
				mid=(lo+hi)/2;
				int cnt=0;
				for(int k=0;k<n;++k){
					if(r[k][i]-r[k][mid-1]==i-mid+1)++cnt;
				}
				if(cnt<=j)res2=mid,lo=mid+1;
				else hi=mid-1;
			}
			pv[i][j]={res,res2};
		}
	}
	for(int i=1;i<=t;++i)dp[0][i]=INF;
	for(int i=1;i<=s;++i)dp[i][0]=INF;
	for(int k=1;k<=s;++k){
		for(int j=0;j<=n;++j){//how many all 1s
			for(int i=1;i<=t;++i){//position
				st[j][0][i]=dp[k-1][i-1]-pfx[i-1]*j;
			}
			for(int k=1;k<15;++k){
				for(int i=1;i+(1<<k)<=t+1;++i){
					st[j][k][i]=min(st[j][k-1][i],st[j][k-1][i+(1<<(k-1))]);
				}
			}
		}
		for(int i=1;i<=t;++i){
			dp[k][i]=INF;
			for(int j=0;j<=n;++j){//how many all 1s
				int x=pv[i][j].fi,y=pv[i][j].se;
				if(x==-1||y==-1||x>y)continue;
				int l=32-__builtin_clz(y-x+1)-1;
				dp[k][i]=min(dp[k][i],j*pfx[i]+min(st[j][l][x],st[j][l][y-(1<<l)+1]));
			}
		}
	}
	for(int i=1;i<=s;++i)pf("%d\n",dp[i][t]);
}

/*
3 5 5
4 3 5 4 3
10110
11011
00101
*/

Subtask #1
8.0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3924 KB Output is correct
2 Correct 25 ms 3804 KB Output is correct
3 Correct 25 ms 3876 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 9308 KB Output is correct
2 Correct 218 ms 12140 KB Output is correct
3 Correct 311 ms 15432 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 27 ms 3924 KB Output is correct
4 Correct 25 ms 3804 KB Output is correct
5 Correct 25 ms 3876 KB Output is correct
6 Correct 136 ms 9308 KB Output is correct
7 Correct 218 ms 12140 KB Output is correct
8 Correct 311 ms 15432 KB Output is correct
9 Correct 555 ms 24068 KB Output is correct
10 Correct 778 ms 31148 KB Output is correct
11 Correct 1847 ms 69196 KB Output is correct
12 Correct 1961 ms 71540 KB Output is correct
13 Correct 1940 ms 71556 KB Output is correct
14 Correct 1939 ms 71660 KB Output is correct
15 Correct 1994 ms 71628 KB Output is correct