oj.uz

Submission #52921

# Submission time Handle Problem Language Result Execution time Memory
52921 2018-06-27T07:37:04 Z tourist(#1970) Popeala (CEOI16_popeala) C++11
26 / 100
 2000 ms 42876 KB 
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll N = 55, T = 20005, inf = 1e12;

ll n, t, s, p[T], a[N][T], dt[N][T], pre[T][N];
char ipt[T];

vector<pll> pot[T];

ll getv (ll S, ll E) {
	ll R = 0;
	for(int i=1;i<=n;i++) {
		if(a[i][E] - a[i][S-1] == E-S+1) R++;
	}
	return R;
}

int main()
{
	scanf("%lld%lld%lld",&n,&t,&s);
	for(int i=1;i<=t;i++) {
		scanf("%lld",&p[i]);
		p[i] += p[i-1];
	}
	for(int i=1;i<=n;i++) {
		scanf("%s",ipt+1);
		for(int j=1;j<=t;j++) {
			a[i][j] = a[i][j-1] + (ipt[j] == '1');
		}
	}
	for(int i=1;i<=t;i++) {
		for(int j=i;;) {
			if(!(1 <= j && j <= t)) break;
			int V = getv(j, i);
			pot[i].push_back({j-1, V});
			if(V == 0) break;
			int S = 0, E = j-1;
			while(S<E) {
				int M = (S+E)/2;
				getv(M+1, i) != V ? S = M+1 : E = M;
			}
			j = S;
		}
	}
	for(int i=1;i<=t;i++) {
		dt[1][i] = getv(1, i) * p[i];
	}
	for(int i=2;i<=s;i++) {
		for(int k=i-1;k<=t;k++) {
			for(int j=0;j<=n;j++) {
				pre[k][j] = dt[i-1][k] - j * p[k];
				if(k >= i) pre[k][j] = min(pre[k-1][j], pre[k][j]);
			}
		}
		for(int j=i;j<=t;j++) {
			dt[i][j] = inf;
			for(auto &T : pot[j]) {
				ll A, B;
				tie(A, B) = T;
				if(A < i-1) continue;
				dt[i][j] = min(dt[i][j], pre[A][B] + B * p[j]);
			}
		}
	}
	for(int i=1;i<=s;i++) {
		printf("%lld\n",dt[i][t]);
	}
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld",&n,&t,&s);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
popeala.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&p[i]);
   ~~~~~^~~~~~~~~~~~~~
popeala.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",ipt+1);
   ~~~~~^~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 888 KB Output is correct
2 Correct 4 ms 1128 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2332 KB Output is correct
2 Correct 21 ms 2364 KB Output is correct
3 Correct 25 ms 2492 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 6000 KB Output is correct
2 Correct 161 ms 8092 KB Output is correct
3 Correct 316 ms 10296 KB Output is correct

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 888 KB Output is correct
2 Correct 4 ms 1128 KB Output is correct
3 Correct 22 ms 2332 KB Output is correct
4 Correct 21 ms 2364 KB Output is correct
5 Correct 25 ms 2492 KB Output is correct
6 Correct 119 ms 6000 KB Output is correct
7 Correct 161 ms 8092 KB Output is correct
8 Correct 316 ms 10296 KB Output is correct
9 Correct 558 ms 15676 KB Output is correct
10 Correct 696 ms 20316 KB Output is correct
11 Execution timed out 2077 ms 42876 KB Time limit exceeded
12 Halted 0 ms 0 KB -