| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 635116 |
2022-08-25T12:36:10 Z |
inksamurai |
Gauss (COCI17_gauss) |
C++17 |
|
1179 ms |
165720 KB |
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
#define int ll
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){
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],(ll)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,(ll)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();
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
410 ms |
164728 KB |
Output is correct |
| 2 |
Correct |
345 ms |
164704 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
395 ms |
164576 KB |
Output is correct |
| 2 |
Correct |
360 ms |
164820 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
390 ms |
164812 KB |
Output is correct |
| 2 |
Correct |
339 ms |
164696 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
358 ms |
164708 KB |
Output is correct |
| 2 |
Correct |
347 ms |
164708 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
821 ms |
165140 KB |
Output is correct |
| 2 |
Correct |
753 ms |
165104 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
633 ms |
165212 KB |
Output is correct |
| 2 |
Correct |
839 ms |
165212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
674 ms |
165196 KB |
Output is correct |
| 2 |
Correct |
1060 ms |
165196 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1179 ms |
165124 KB |
Output is correct |
| 2 |
Correct |
643 ms |
165516 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
918 ms |
165164 KB |
Output is correct |
| 2 |
Correct |
596 ms |
165464 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
778 ms |
165240 KB |
Output is correct |
| 2 |
Correct |
952 ms |
165720 KB |
Output is correct |
