oj.uz

Submission #287442

# Submission time Handle Problem Language Result Execution time Memory
287442 2020-08-31T17:04:19 Z Namnamseo Popeala (CEOI16_popeala) C++17
26 / 100
 2000 ms 35196 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2432 KB Output is correct
2 Correct 50 ms 19456 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 27508 KB Output is correct
2 Correct 231 ms 26476 KB Output is correct
3 Correct 238 ms 27512 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 27324 KB Output is correct
2 Correct 380 ms 28672 KB Output is correct
3 Correct 483 ms 29164 KB Output is correct

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2432 KB Output is correct
2 Correct 50 ms 19456 KB Output is correct
3 Correct 241 ms 27508 KB Output is correct
4 Correct 231 ms 26476 KB Output is correct
5 Correct 238 ms 27512 KB Output is correct
6 Correct 316 ms 27324 KB Output is correct
7 Correct 380 ms 28672 KB Output is correct
8 Correct 483 ms 29164 KB Output is correct
9 Correct 702 ms 30364 KB Output is correct
10 Correct 746 ms 31232 KB Output is correct
11 Execution timed out 2009 ms 35196 KB Time limit exceeded
12 Halted 0 ms 0 KB -