oj.uz

Submission #52930

# Submission time Handle Problem Language Result Execution time Memory
52930 2018-06-27T07:56:36 Z tourist(#1970) Popeala (CEOI16_popeala) C++11
100 / 100
 633 ms 57856 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], nxt[N][T];
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] = (ipt[j] == '1');
			nxt[i][j] = (a[i][j] ? nxt[i][j-1] : j);
			a[i][j] += a[i][j-1];
		}
	}
	for(int i=1;i<=t;i++) {
		for(int j=1;j<=n;j++) {
			if(!nxt[j][i]) continue;
			pot[i].push_back({nxt[j][i]-1, getv(nxt[j][i], i)});
		}
		pot[i].push_back({i-1, getv(i, i)});
	}
	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 1384 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2832 KB Output is correct
2 Correct 13 ms 2876 KB Output is correct
3 Correct 14 ms 2956 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 7356 KB Output is correct
2 Correct 92 ms 9556 KB Output is correct
3 Correct 87 ms 12116 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 888 KB Output is correct
2 Correct 4 ms 1384 KB Output is correct
3 Correct 13 ms 2832 KB Output is correct
4 Correct 13 ms 2876 KB Output is correct
5 Correct 14 ms 2956 KB Output is correct
6 Correct 49 ms 7356 KB Output is correct
7 Correct 92 ms 9556 KB Output is correct
8 Correct 87 ms 12116 KB Output is correct
9 Correct 156 ms 18516 KB Output is correct
10 Correct 205 ms 23996 KB Output is correct
11 Correct 612 ms 52584 KB Output is correct
12 Correct 544 ms 54296 KB Output is correct
13 Correct 633 ms 55524 KB Output is correct
14 Correct 596 ms 56804 KB Output is correct
15 Correct 591 ms 57856 KB Output is correct