Submission #287442

#	Time	Username	Problem	Language	Result	Execution time	Memory
287442		Namnamseo	Popeala (CEOI16_popeala)	C++17	26 / 100	2009 ms	35196 KiB

popeala

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

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]
    6 | 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]
    7 | 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]
   28 |   scanf("%s", _buf + 1);
      |   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 0 / 74