Submission #551151

#	Time	Username	Problem	Language	Result	Execution time	Memory
551151		DanerZein	Let's Win the Election (JOI22_ho_t3)	C++14	56 / 100	2656 ms	1004328 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<double,double> dd;
const int MAX=1e9;
bool orden(dd a,dd b){
  if(a.second==b.second) return a.first<b.first;
  return a.second<b.second;
}
int n;
vector<dd> st;
double ka;
double dp[510][510][510];
double knap(int id,int k,int ca){
  if(dp[id][k][ca]!=-1) return dp[id][k][ca];
  if(id==n) {
    if(ca==0 && k==ka) return 0;
    return MAX;
  }
  double ans=knap(id+1,k,ca);
  if(ca!=0){
    ans=min(ans,knap(id+1,k,ca-1)+st[id].first/(ka+1));
    if(k!=ka)
      ans=min(ans,knap(id+1,k+1,ca-1)+st[id].second/(double)(k+1));
  }
  return dp[id][k][ca]=ans;
}
int main(){
  int k; scanf("%d%d",&n,&k);
  for(int i=0;i<n;i++){
    int a,b; scanf("%d%d",&a,&b);
    if(b==-1) b=MAX;
    st.push_back(dd(a,b));
  }
  sort(st.begin(),st.end(),orden);
  double res=MAX;
  for(int i=0;i<k;i++){
    ka=i;
    for(int id=0;id<=n;id++) for(int kk=0;kk<=n;kk++) for(int ca=0;ca<=n;ca++) dp[id][kk][ca]=-1;
    double rp=knap(0,0,k);
    //cout<<i<<": "<<rp<<endl;
    res=min(res,rp);
  }
  printf("%.15f\n",res);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:29:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |   int k; scanf("%d%d",&n,&k);
      |          ~~~~~^~~~~~~~~~~~~~
Main.cpp:31:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |     int a,b; scanf("%d%d",&a,&b);
      |              ~~~~~^~~~~~~~~~~~~~

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