oj.uz

Submission #537029

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

#pragma GCC optimize("-O3")
#pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")
#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;

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};
		}
	}
	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
*/

Compilation message

popeala.cpp:5: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    5 | #pragma comment(linker, "/stack:200000000")
      | 
popeala.cpp: In function 'int main()':
popeala.cpp:23:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |  sf("%d%d%d",&n,&t,&s);
      |    ^
popeala.cpp:25:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |   sf("%d",&p[i]);
      |     ^
popeala.cpp:30:6: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |    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 1 ms 1492 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3824 KB Output is correct
2 Correct 24 ms 3768 KB Output is correct
3 Correct 26 ms 3924 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 9260 KB Output is correct
2 Correct 228 ms 12152 KB Output is correct
3 Correct 298 ms 15472 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 1 ms 1492 KB Output is correct
3 Correct 27 ms 3824 KB Output is correct
4 Correct 24 ms 3768 KB Output is correct
5 Correct 26 ms 3924 KB Output is correct
6 Correct 162 ms 9260 KB Output is correct
7 Correct 228 ms 12152 KB Output is correct
8 Correct 298 ms 15472 KB Output is correct
9 Correct 556 ms 24108 KB Output is correct
10 Correct 782 ms 31144 KB Output is correct
11 Correct 1913 ms 69320 KB Output is correct
12 Execution timed out 2059 ms 71528 KB Time limit exceeded
13 Halted 0 ms 0 KB -