Submission #703929

#	Time	Username	Problem	Language	Result	Execution time	Memory
703929		niter	Let's Win the Election (JOI22_ho_t3)	C++14	100 / 100	142 ms	1356 KiB

Main

#include<stdio.h>
#include<algorithm>
#define R register int
#define D double
#define I inline
#define INF 999999999
I void Min(D&x,const D y){
	if(x>y){
		x=y;
	}
}
struct State{
	int ValA,ValB;
	I void Read(){
		scanf("%d%d",&ValA,&ValB);
		if(ValB==-1){
			ValB=INF;
		}
	}
	I friend bool operator<(State A,State B){
		return A.ValB<B.ValB;
	}
}s[501];
D f[501],g[501];
int suf[502][501];
int main(){
	int n,m;
	scanf("%d %d",&n,&m);
	for(R i=1;i<=n;i++){
		s[i].Read();
	}
	std::sort(s+1,s+n+1);
	for(R i=n;i!=0;i--){
		for(R j=n-i+1;j!=0;j--){
			suf[i][j]=suf[i+1][j-1]+s[i].ValA;
		}
		for(R j=1;j<=n-i;j++){
			if(suf[i+1][j]<suf[i][j]){
				suf[i][j]=suf[i+1][j];
			}
		}
	}
	D ans=suf[1][m];
	for(R i=1;i<=m;i++){
		D inv=1/(1.0+i);
		f[0]=0;
		for(R j=1;j<=n&&j<=m;j++){
			for(R k=0;k<=j&&k<=i;k++){
				g[k]=INF;
			}
			for(R k=0;k!=j&&k<=i;k++){
				Min(g[k],f[k]+inv*s[j].ValA);
				Min(g[k+1],f[k]+s[j].ValB/(1.0+k));
			}
			for(R k=0;k<=j&&k<=i;k++){
				f[k]=g[k];
			}
			if(j>=i){
				Min(ans,f[i]+inv*suf[j+1][m-j]);
			}
		}
	}
	printf("%.9lf",ans);
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |  scanf("%d %d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~~
Main.cpp: In member function 'void State::Read()':
Main.cpp:15:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |   scanf("%d%d",&ValA,&ValB);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 33 / 33
• Subtask 6: 11 / 11
• Subtask 7: 23 / 23