oj.uz

Submission #609320

# Submission time Handle Problem Language Result Execution time Memory
609320 2022-07-27T13:44:56 Z UncoolAnon Popeala (CEOI16_popeala) C++17
26 / 100
 2000 ms 14432 KB 
#include <bits/stdc++.h> 
#define ll long long 
using namespace std; 
const int inf=2e9+1,N=5e4+1; 

struct Line {
	mutable ll k, m, p;
	bool operator<(const Line& o) const { return k < o.k; }
	bool operator<(ll x) const { return p < x; }
};
struct LineContainer : multiset<Line, less<>> {
	// (for doubles, use inf = 1/.0, div(a,b) = a/b)
	static const ll inf = LLONG_MAX;
	ll div(ll a, ll b) { // floored division
		return a / b - ((a ^ b) < 0 && a % b); }
	bool isect(iterator x, iterator y) {
		if (y == end()) return x->p = inf, 0;
		if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
		else x->p = div(y->m - x->m, x->k - y->k);
		return x->p >= y->p;
	}
	void add(ll k, ll m) {
		auto z = insert({k, m, 0}), y = z++, x = y;
		while (isect(y, z)) z = erase(z);
		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
		while ((y = x) != begin() && (--x)->p >= y->p)
			isect(x, erase(y));
	}
	ll query(ll x) {
		assert(!empty());
		auto l = *lower_bound(x);
		return l.k * x + l.m;
	}
};
vector<LineContainer> sg(N*4); 
void update(int i,int l,int r,int index, int slope,int yin){
	if(index<l||r<index) return ; 
	sg[i].add(slope,yin); 
	if(l!=r){
		update(i*2,l,(r+l)/2,index,slope,yin); 
		update(i*2+1,(r+l)/2+1,r,index,slope,yin); 
	}
	return ; 
}
int query(int i,int l,int r, int ql ,int qr,int point){
	if(qr<l||r<ql||sg[i].empty()) return -inf;
	if(ql<=l&&r<=qr){
		return sg[i].query(point); 
	}
	return max(query(i*2,l,(r+l)/2,ql,qr,point),query(i*2+1,(r+l)/2+1,r,ql,qr,point)); 
}
signed main(){
	int n,t,s; 
	cin>>n>>t>>s; 
	vector<vector<int>> dp(s+1,vector<int>(t+1,inf)); 
	for(int i=0;i<t;i++) dp[0][i]=0; 
	vector<int> v(t); 
	for(int&x:v) cin>>x; 
	vector<int> prefix=v; 
	for(int i=1;i<t;i++) prefix[i]+=prefix[i-1]; 
	vector<vector<char>> a(n,vector<char>(t)); 
	for(int i=0;i<n;i++)
		for(int j=0;j<t;j++)
			cin>>a[i][j]; 
	vector<vector<int>> last(n,vector<int>(t,-1)); 
	for(int i=0;i<n;i++){
		for(int j=0;j<t;j++){
			if(a[i][j]=='0') last[i][j]=j;
			else if(j) last[i][j]=last[i][j-1]; 
		}
	}

	for(int subs=1;subs<=s;++subs){
		for(int testcase=0;testcase<t;testcase++){
			vector<int> pl; 
			for(int contestant=0;contestant<n;contestant++) pl.push_back(last[contestant][testcase]); 
			sort(pl.begin(),pl.end()); 
			int cnt=0; 
			for(int&x:pl) cnt+=(x==-1) ; 
				if(subs==1)
					dp[subs][testcase]=prefix[testcase]*cnt; 
				else{
					if(testcase) dp[subs][testcase]=dp[subs-1][testcase-1]+v[testcase]*n; 
				}
				if(subs==1) continue ; 
			for(int i=0;i<pl.size();i++){
				if(pl[i]==-1) continue; 
				int da=-query(1,0,t,0,pl[i]-1,i); 
				if(pl[i]) dp[subs][testcase]=min(dp[subs][testcase],da+prefix[testcase]*i);  
				else{
					if(subs==1) dp[subs][testcase]=min(dp[subs][testcase],prefix[testcase]*i);
				}
			}
		}
		for(int i=0;i<t*4;i++) sg[i].clear(); 

		for(int testcase=0;testcase<t;testcase++){
			update(1,0,t,testcase,prefix[testcase],-dp[subs][testcase]); 
		}
	}
	for(int i=1;i<=s;i++) cout<<dp[i][t-1]<<endl;
	return 0; 
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:87:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |    for(int i=0;i<pl.size();i++){
      |                ~^~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 10068 KB Output is correct
2 Correct 140 ms 10068 KB Output is correct
3 Correct 163 ms 10184 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 809 ms 11368 KB Output is correct
2 Correct 1136 ms 12028 KB Output is correct
3 Correct 1506 ms 12760 KB Output is correct

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 149 ms 10068 KB Output is correct
4 Correct 140 ms 10068 KB Output is correct
5 Correct 163 ms 10184 KB Output is correct
6 Correct 809 ms 11368 KB Output is correct
7 Correct 1136 ms 12028 KB Output is correct
8 Correct 1506 ms 12760 KB Output is correct
9 Execution timed out 2054 ms 14432 KB Time limit exceeded
10 Halted 0 ms 0 KB -