oj.uz

답안 #46208

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
46208 2018-04-18T01:27:19 Z sorry_Benq 조교 (CEOI16_popeala) C++17
100 / 100
 1309 ms 16224 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]; //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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1272 KB Output is correct
2 Correct 4 ms 1640 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 2208 KB Output is correct
2 Correct 35 ms 2208 KB Output is correct
3 Correct 36 ms 2288 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 161 ms 3136 KB Output is correct
2 Correct 223 ms 3568 KB Output is correct
3 Correct 255 ms 3948 KB Output is correct

Subtask #4
74.0 / 74.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1272 KB Output is correct
2 Correct 4 ms 1640 KB Output is correct
3 Correct 39 ms 2208 KB Output is correct
4 Correct 35 ms 2208 KB Output is correct
5 Correct 36 ms 2288 KB Output is correct
6 Correct 161 ms 3136 KB Output is correct
7 Correct 223 ms 3568 KB Output is correct
8 Correct 255 ms 3948 KB Output is correct
9 Correct 365 ms 5356 KB Output is correct
10 Correct 582 ms 6508 KB Output is correct
11 Correct 1105 ms 11260 KB Output is correct
12 Correct 1146 ms 12648 KB Output is correct
13 Correct 1309 ms 14040 KB Output is correct
14 Correct 1309 ms 15236 KB Output is correct
15 Correct 1269 ms 16224 KB Output is correct