oj.uz

답안 #537032

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
537032 2022-03-14T09:50:56 Z jamezzz 조교 (CEOI16_popeala) C++17
26 / 100
 2000 ms 71600 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;

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

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 3896 KB Output is correct
2 Correct 25 ms 3720 KB Output is correct
3 Correct 26 ms 3920 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 164 ms 9256 KB Output is correct
2 Correct 265 ms 12184 KB Output is correct
3 Correct 328 ms 15344 KB Output is correct

Subtask #4
0 / 74.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 26 ms 3896 KB Output is correct
4 Correct 25 ms 3720 KB Output is correct
5 Correct 26 ms 3920 KB Output is correct
6 Correct 164 ms 9256 KB Output is correct
7 Correct 265 ms 12184 KB Output is correct
8 Correct 328 ms 15344 KB Output is correct
9 Correct 587 ms 24096 KB Output is correct
10 Correct 797 ms 31396 KB Output is correct
11 Correct 1927 ms 69308 KB Output is correct
12 Correct 1987 ms 71592 KB Output is correct
13 Execution timed out 2063 ms 71600 KB Time limit exceeded
14 Halted 0 ms 0 KB -