Submission #63162

#	Time	Username	Problem	Language	Result	Execution time	Memory
63162		khsoo01	Popeala (CEOI16_popeala)	C++11	100 / 100	926 ms	60120 KiB

popeala

#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 (stderr)

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 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 74 / 74