oj.uz

Submission #46204

# Submission time Handle Problem Language Result Execution time Memory
46204 2018-04-18T00:58:50 Z sorry_Benq Popeala (CEOI16_popeala) C++17
26 / 100
 2000 ms 4028 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
int N, T, S; 
int points[20005];
int prefixpoints[20005];
bool solves[52][20005];
int presolve[52][20005];
int DP1[20005];
int DP2[20005];
int ranges[20005][52]; //M[j][k] is the min value of i s.t. cnt(i. j) >= k;

int INF = 2000000005;

struct MinDeque { 
    int lo = 1, hi = 0;
    deque<pii> d;
    
    void ins(int x) { // add to back
        while (sz(d) && d.back().f >= x) d.pop_back();
        d.pb({x,++hi});
    }
    
    void del() { // delete from front
        if (d.front().s == lo++) d.pop_front();
    }
    
    int get() { 
        return sz(d) ? d.front().f : INF;
    }
};

int cnt(int i, int j){
	int res = 0;
	for (int x = 1; x <= N; x++){
		if (presolve[x][j] - presolve[x][i - 1] == j - i + 1){
			res += 1;
		}
	}
	return res;
}

int score(int i, int j){
	//value of one indexed [i, j] inclusive interval
	int val = prefixpoints[j] - prefixpoints[i - 1];
	int res = 0;
	for (int x = 1; x <= N; x++){
		if (presolve[x][j] - presolve[x][i - 1] == j - i + 1){
			res += val;
		}
	} 
	return res;
}

void fill(int idx, int L, int R, int lo, int hi){
	if (lo == hi){
		for (int i = L; i <= R; i++){
			ranges[idx][i] = lo;
		}
		return;
	}
	else{
		int mid = (lo + hi)/2;
		int k = cnt(mid, idx);
		fill(idx, L, k, lo, mid);
		fill(idx, k+1, R, mid + 1, hi);
	}
}

int main(){
	cin >> N >> T >> S;
	for (int i = 1; i <= T; i++){
		cin >> points[i];
	}
	prefixpoints[0] = 0;
	for (int i = 1; i <= T; i++){
		prefixpoints[i] = prefixpoints[i - 1] + points[i];
	}
	for (int i = 1; i <= N; i++){
		string s; cin >> s;
		for (int j = 1; j <= T; j++){
			solves[i][j] = (s[j - 1] - '0');
		}
		presolve[i][0] = 0;
		for (int j = 1; j <= T; j++){
			presolve[i][j] = solves[i][j] + presolve[i][j - 1];
		}
	}
	
	for (int i = 1; i <= T; i++){
		int bnd = cnt(i, i);
		fill(i, 0, bnd, 1, i);
		/*for (int j = 0; j <= bnd; j++){
			int lo = 1;
			int hi = i;
			while (lo != hi){
				int mid = (lo + hi)/2;
				if (cnt(mid, i) < j){
					lo = mid + 1;
				}
				else{
					hi = mid;
				}
			}
			ranges[i][j] = lo;
		}*/
		for (int j = bnd + 1; j <= N + 1; j++){
			ranges[i][j] = INF;
		}
	}
	
	for (int j = 1; j <= T; j++){
		DP2[j] = score(1, j);
	}
	DP2[0] = INF;
	cout << DP2[T] << endl;
	for (int i = 2; i <= S; i++){
		for (int j = 1; j <= T; j++){
			DP1[j] = DP2[j];
		}
		for (int j = 0; j < i; j++){
			DP2[j] = INF;
		}
		MinDeque M[N + 1];
		for (int j = i; j <= T; j++){
			for (int k = 0; k <= N; k++){
				while (M[k].hi < min(j, ranges[j][k + 1] - 1) - 1){
					M[k].ins(DP1[M[k].hi + 1] - k*prefixpoints[M[k].hi + 1]);
				} 
				while (M[k].lo < min(j, ranges[j][k]) - 1){
					M[k].del();
				}
			} 
			DP2[j] = INF;
			for (int k = 0; k <= N; k++){
				if (M[k].get() < INF){
					//cout << i << ' ' << j << ' ' << M[k].get() << ' ' << M[k].lo << ' ' << M[k].hi << ' ' << k << endl;
					DP2[j] = min(DP2[j], k*prefixpoints[j] + M[k].get());
				}
			}
			//cout << i << ' ' << j << ' ' << DP2[j] << endl;
		}
		cout << DP2[T] << endl;
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 744 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 1068 KB Output is correct
2 Correct 42 ms 1068 KB Output is correct
3 Correct 45 ms 1132 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 1992 KB Output is correct
2 Correct 629 ms 2368 KB Output is correct
3 Correct 972 ms 2864 KB Output is correct

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 744 KB Output is correct
3 Correct 46 ms 1068 KB Output is correct
4 Correct 42 ms 1068 KB Output is correct
5 Correct 45 ms 1132 KB Output is correct
6 Correct 363 ms 1992 KB Output is correct
7 Correct 629 ms 2368 KB Output is correct
8 Correct 972 ms 2864 KB Output is correct
9 Execution timed out 2064 ms 4028 KB Time limit exceeded
10 Halted 0 ms 0 KB -