제출 #635070

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
635070		inksamurai	Gauss (COCI17_gauss)	C++17	48 / 160	2079 ms	82596 KiB

gauss

#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

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

void slv(){
	int ans=0;
	rep(_,m){
		int now=inf;
		int need=l[_];
		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(k,loq){
					if(fdp[k]==inf or k>need) continue;
					now=min(now,fdp[k]+(need-k)*w);
				}
			}
		}
		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 / 16
• Subtask 2: 0 / 16
• Subtask 3: 16 / 16
• Subtask 4: 16 / 16
• Subtask 5: 0 / 16
• Subtask 6: 0 / 16
• Subtask 7: 0 / 16
• Subtask 8: 0 / 16
• Subtask 9: 0 / 16
• Subtask 10: 0 / 16