oj.uz

Submission #52927

# Submission time Handle Problem Language Result Execution time Memory
52927 2018-06-27T07:52:07 Z tourist(#1970) Popeala (CEOI16_popeala) C++11
0 / 100
 45 ms 7260 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<=n;i++) {
		for(int j=1;j<=t;j++) {
			if(!nxt[i][j]) continue;
			pot[j].push_back({nxt[i][j]-1, getv(nxt[i][j], j)});
		}
	}
	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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 888 KB Output is correct
2 Incorrect 2 ms 1256 KB Output isn't correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 2848 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 7260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 888 KB Output is correct
2 Incorrect 2 ms 1256 KB Output isn't correct