Submission #46208

#	Time	Username	Problem	Language	Result	Execution time	Memory
46208		sorry_Benq	Popeala (CEOI16_popeala)	C++17	100 / 100	1309 ms	16224 KiB

popeala

#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]; //ranges[j][k] is the min positive integer 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 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;
}

bool on[51]; //these all start as false
int val[51];
vector<int> entry[20005];
vector<int> back[20005];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	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');
		}
		for (int j = 1; j <= T; j++){
			if (solves[i][j] == true){
				if (solves[i][j-1] == false){
					entry[j].push_back(i);
				}
				if (solves[i][j+1] == false){
					back[j].push_back(i);
				}
			}
		}
		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++){
		vector<int> v;
		for (int j: entry[i]){
			on[j] = true;
			val[j] = i;
		}
		for (int j = 1; j <= N; j++){
			if (on[j]){
				v.push_back(val[j]);
			}
		}
		sort(v.begin(), v.end());
		ranges[i][0] = 1;
		for (int j = 1; j <= v.size(); j++){
			ranges[i][j] = v[j - 1];
		}
		for (int j = v.size() + 1; j <= N + 1; j++){
			ranges[i][j] = INF;
		}
		for (int j: back[i]){
			on[j] = false;
		}
	}
	
	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;
	}
}

Compilation message (stderr)

popeala.cpp: In function 'int main()':
popeala.cpp:118:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 1; j <= v.size(); j++){
                   ~~^~~~~~~~~~~

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