oj.uz

Submission #537024

# Submission time Handle Problem Language Result Execution time Memory
537024 2022-03-14T09:45:36 Z jamezzz Popeala (CEOI16_popeala) C++17
26 / 100
 2000 ms 66940 KB 
#include <bits/stdc++.h>
using namespace std;

#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;

int main(){
	sf("%d%d%d",&n,&t,&s);
	for(int i=1;i<=t;++i){
		sf("%d",&p[i]);
		pfx[i]=p[i]+pfx[i-1];
	}
	for(int i=0;i<n;++i){
		for(int j=1;j<=t;++j){
			sf(" %c",&ch);
			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};
			//pf("%d %d: %d %d\n",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]));
			}
			//pf("%d ",dp[k][i]);
		}
		//pf("\n");
	}
	for(int i=1;i<=s;++i)pf("%d\n",dp[i][t]);
}

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

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:17:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |  sf("%d%d%d",&n,&t,&s);
      |    ^
popeala.cpp:19:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |   sf("%d",&p[i]);
      |     ^
popeala.cpp:24:6: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |    sf(" %c",&ch);
      |      ^

Subtask #1
8.0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 3916 KB Output is correct
2 Correct 43 ms 3740 KB Output is correct
3 Correct 56 ms 3900 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 9332 KB Output is correct
2 Correct 336 ms 12136 KB Output is correct
3 Correct 522 ms 15368 KB Output is correct

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 1492 KB Output is correct
3 Correct 45 ms 3916 KB Output is correct
4 Correct 43 ms 3740 KB Output is correct
5 Correct 56 ms 3900 KB Output is correct
6 Correct 225 ms 9332 KB Output is correct
7 Correct 336 ms 12136 KB Output is correct
8 Correct 522 ms 15368 KB Output is correct
9 Correct 870 ms 24044 KB Output is correct
10 Correct 1102 ms 31224 KB Output is correct
11 Execution timed out 2076 ms 66940 KB Time limit exceeded
12 Halted 0 ms 0 KB -