PKU 1297-supermarket

苦労したけど割と綺麗なコードも書けたし載せます

最初は普通にDPやってMLEー＞
メモリを2回分だけとるようにしたけどTLEー＞
cinをscanfにしたけどWAー＞
printfのフォーマットを直してAC
scanfはdouble型を受けとるときlfだけどprintfはfなんですね
これで5回ぐらいWA出してました。

vector<vector<double> >dp(2,vector<double>(110));
int main(){
	int m,n;
	while(scanf("%d%d",&m,&n) && (n||m)){
		vi toget(m);
		vector<pair<int,double> >product(n);
		REP(i,m) scanf("%d",&toget[i]);
		REP(i,n) scanf("%d%lf",&product[i].fr,&product[i].sc);
		toget.pb(INF);
		REP(i,2) REP(j,m+1) dp[i][j]=INF;
		dp[0][0]=0;
		REP(i,n){
			REP(j,m+1){
				if(dp[0][j]==INF) continue;
				if(toget[j]==product[i].fr){
					dp[1][j+1]=min(dp[0][j]+product[i].sc,dp[1][j+1]);
				}
				dp[1][j]=min(dp[1][j],dp[0][j]);
			}
			swap(dp[0],dp[1]);
			fill(ALL(dp[1]),INF);
		}
		if(dp[0][m]==INF) cout<<"Impossible"<<endl;
		else printf("%.2f\n", dp[0][m]);
	}
	return 0;
}