oj.uz

Submission #635122

# Submission time Handle Problem Language Result Execution time Memory
635122 2022-08-25T12:40:11 Z inksamurai Gauss (COCI17_gauss) C++17
96 / 160
 1076 ms 165344 KB 
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3PGDklf ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e

// kactl line container
// cht on max point
// use monotocity if possible
// o(nlgn)

// APIO'10 P1
// DMOJ Yet Another Contest 2 P6 - Travel Budget
// JOISC'21 bodyguard

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;
	}
};

const ll inf=1e10;
const int _n=1e4,_m=50,_q=1e6+1,loq=20;

int k,m,t,q,_a,_b;
ll f[_n],l[_n],sid[_q],dp[loq][_q];
pair<ll,ll> rbts[_m];

void _gap_dp(){
	rng(i,1,_q){
		for(int j=i;j<_q;j+=i){
			sid[j]+=1;
		}
	}
	rep(k,loq){
		rep(i,_q){
			dp[k][i]=inf;
		}
	}
	dp[0][1]=0;
	rep(k,loq-1){
		rng(i,1,_q){
			if(dp[k][i]==inf) continue;
			for(int j=2*i;j<_q;j+=i){
				dp[k+1][j]=min(dp[k+1][j],dp[k][i]+f[sid[j/i]]);
			}
		}
	}
}

ll fdp[loq],gdp[loq];

void slv(){
	rep(i,loq){
		gdp[i]=inf;
	}
	LineContainer cht;
	rep(i,t){
		auto [ra,w]=rbts[i];
		if(_a%ra==0 and ra%_b==0){
			int l=_a/ra;
			int r=ra/_b;
			rep(k,loq){
				fdp[k]=inf;
			}
			rep(j,loq){
				per(nj,j+1){
					if(j+nj<loq){
						fdp[j+nj]=min(fdp[j+nj],min(dp[j][r]+dp[nj][l],dp[j][l]+dp[nj][r]));
					}
				}
			}
			rep(j,loq){
				if(fdp[j]<inf){
					ll cof=w;
					ll ad=-j*w+fdp[j];
					cht.add(-cof,-ad);
				}
				per(nj,j+1){
					if(fdp[nj]<inf){
						gdp[j]=min(gdp[j],(j-nj)*w+fdp[nj]);
					}
				}
			}
		}
	}
	int ans=0;
	rep(_,m){
		ll now=1e18;
		int need=l[_];
		if(need<loq){
			now=min(now,dp[need][_a/_b]);
			now=min(now,gdp[need]);
			// print(gdp[need]);
		}else if(sz(cht)){
			now=min(now,-cht.query(need));
		}
		ans+=(now>=inf?-1:now);
	}
	print(ans);
}

signed main(){
_3PGDklf;
	cin>>k;
	rep(i,k){
		cin>>f[i+1];
	}
	cin>>m;
	rep(i,m){
		cin>>l[i];
	}
	cin>>t;
	rep(i,t){
		cin>>rbts[i].fi>>rbts[i].se;
	}
	_gap_dp();
	cin>>q;
	rep(_,q){
		cin>>_a>>_b;
		if(_a%_b){
			print(-m);
		}else{
			slv();
		}
	}
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 164692 KB Output is correct
2 Correct 370 ms 164700 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 164700 KB Output is correct
2 Correct 378 ms 164700 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 392 ms 164696 KB Output is correct
2 Correct 385 ms 164704 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 341 ms 164584 KB Output is correct
2 Correct 351 ms 164612 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 894 ms 165192 KB Output is correct
2 Correct 748 ms 165256 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 575 ms 165172 KB Output is correct
2 Correct 866 ms 165212 KB Output is correct

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 633 ms 165084 KB Output is correct
2 Incorrect 1076 ms 165344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 1058 ms 165216 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 932 ms 165216 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 766 ms 165236 KB Output isn't correct
2 Halted 0 ms 0 KB -