Submission #635111

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
635111	2022-08-25T12:32:52 Z	inksamurai	Gauss (COCI17_gauss)	C++17	Compilation error	0 ms	0 KB

gauss

#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 int inf=1e9;
const int _n=1e4,_m=50,_q=1e6+1,loq=20;

int k,m,t,q,_a,_b;
int f[_n],l[_n],sid[_q],dp[loq][_q];
pii 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){
			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]]);
			}
		}
	}
}

int 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){
					int cof=w;
					int 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=2e9;
		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();
		}
	}
}

Compilation message

gauss.cpp: In function 'void slv()':
gauss.cpp:132:31: error: no matching function for call to 'min(ll&, int&)'
  132 |    now=min(now,dp[need][_a/_b]);
      |                               ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from gauss.cpp:4:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
gauss.cpp:132:31: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  132 |    now=min(now,dp[need][_a/_b]);
      |                               ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from gauss.cpp:4:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
gauss.cpp:132:31: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  132 |    now=min(now,dp[need][_a/_b]);
      |                               ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from gauss.cpp:4:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3468 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
gauss.cpp:132:31: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  132 |    now=min(now,dp[need][_a/_b]);
      |                               ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from gauss.cpp:4:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note:   template argument deduction/substitution failed:
gauss.cpp:132:31: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  132 |    now=min(now,dp[need][_a/_b]);
      |                               ^
gauss.cpp:133:25: error: no matching function for call to 'min(ll&, int&)'
  133 |    now=min(now,gdp[need]);
      |                         ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from gauss.cpp:4:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
gauss.cpp:133:25: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  133 |    now=min(now,gdp[need]);
      |                         ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from gauss.cpp:4:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
gauss.cpp:133:25: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  133 |    now=min(now,gdp[need]);
      |                         ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from gauss.cpp:4:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3468 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
gauss.cpp:133:25: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  133 |    now=min(now,gdp[need]);
      |                         ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from gauss.cpp:4:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note:   template argument deduction/substitution failed:
gauss.cpp:133:25: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  133 |    now=min(now,gdp[need]);
      |                         ^