oj.uz

답안 #52879

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
52879 2018-06-27T06:08:26 Z Petr(#1971) 조교 (CEOI16_popeala) C++11
100 / 100
 1683 ms 35684 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define x first
#define y second

int n, t, s;

int ps[20001];
int pl[51][20001];

char _buf[20010];
void in(){
	read(n, t, s);
	for(int i=1; i<=t; ++i){
		read(ps[i]); ps[i] += ps[i-1];
	}
	for(int i=0; i<n; ++i){
		scanf("%s", _buf + 1);
		for(int j=1; j<=t; ++j){
			if(_buf[j] == '1')
				pl[i][j] = pl[i][j-1] + 1;
		}
	}
}

ll dpr[2][20001];
ll *dp = dpr[0], *bef = dpr[1];

const ll inf = 1ll<<40;
const int M = 32768;
ll tree[52][M<<1];
ll rmin(int row,int l,int r){
	ll ret=inf;
	for(l+=M, r+=M; l<=r; l/=2, r/=2){
		if(l%2==1) ret=min(ret, tree[row][l++]);
		if(r%2==0) ret=min(ret, tree[row][r--]);
	}
	return ret;
}

int ls[20001][52];

int main()
{
	in();
	fill(dp+1, dp+t+1, inf);
	swap(dp, bef);
	
	for(int i=1; i<=t; ++i){
		for(int j=1; j<=n; ++j) ls[i][j] = pl[j-1][i];
		ls[i][0] = 0; ls[i][n+1] = i;
		sort(ls[i], ls[i]+n+2);
	}
	
	for(int ts=1; ts<=s; ++ts){
		for(int c=0; c<=n+1; ++c){
			fill(tree[c]+M, tree[c]+2*M, inf);
			for(int i=ts-1; i<=t; ++i){
				tree[c][M+i] = bef[i] - c*ps[i];
			}
			for(int i=M-1; 1<=i; --i) tree[c][i]=min(tree[c][2*i], tree[c][2*i+1]);
		}
		
		fill(dp, dp+ts, inf);
		for(int i=ts; i<=t; ++i){
			ll d = inf;
			for(int c=0; c<=n; ++c){
				d = min(d, rmin(n-c, i-ls[i][c+1], i-ls[i][c]-1) + (n-c)*ps[i]);
			}
			dp[i] = d;
		}
		printf("%lld\n", dp[t]);
		swap(dp, bef);
	}
	return 0;
}

Compilation message

popeala.cpp: In function 'void read(int&)':
popeala.cpp:6:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void read(int& x){ scanf("%d",&x); }
                    ~~~~~^~~~~~~~~
popeala.cpp: In function 'void read(ll&)':
popeala.cpp:7:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void read(ll& x){ scanf("%lld",&x); }
                   ~~~~~^~~~~~~~~~~
popeala.cpp: In function 'void in()':
popeala.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", _buf + 1);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2424 KB Output is correct
2 Correct 57 ms 19684 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 256 ms 27700 KB Output is correct
2 Correct 247 ms 27700 KB Output is correct
3 Correct 277 ms 27700 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 325 ms 27700 KB Output is correct
2 Correct 381 ms 28732 KB Output is correct
3 Correct 484 ms 29244 KB Output is correct

Subtask #4
74.0 / 74.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2424 KB Output is correct
2 Correct 57 ms 19684 KB Output is correct
3 Correct 256 ms 27700 KB Output is correct
4 Correct 247 ms 27700 KB Output is correct
5 Correct 277 ms 27700 KB Output is correct
6 Correct 325 ms 27700 KB Output is correct
7 Correct 381 ms 28732 KB Output is correct
8 Correct 484 ms 29244 KB Output is correct
9 Correct 594 ms 30204 KB Output is correct
10 Correct 705 ms 30924 KB Output is correct
11 Correct 1484 ms 34488 KB Output is correct
12 Correct 1683 ms 35656 KB Output is correct
13 Correct 1561 ms 35668 KB Output is correct
14 Correct 1472 ms 35684 KB Output is correct
15 Correct 1598 ms 35684 KB Output is correct