oj.uz

Submission #635072

# Submission time Handle Problem Language Result Execution time Memory
635072 2022-08-25T11:39:39 Z inksamurai Gauss (COCI17_gauss) C++17
48 / 160
 2000 ms 82636 KB 
#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=1e7;
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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1592 ms 82508 KB Output is correct
2 Correct 1583 ms 82516 KB Output is correct

Subtask #2
0 / 16.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1634 ms 82504 KB Output is correct
2 Correct 1592 ms 82512 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1624 ms 82512 KB Output is correct
2 Correct 1626 ms 82512 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2086 ms 82508 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2089 ms 82508 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2093 ms 82636 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2086 ms 82488 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2091 ms 82464 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2089 ms 82440 KB Time limit exceeded
2 Halted 0 ms 0 KB -