oj.uz

답안 #551517

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
551517 2022-04-20T23:16:55 Z DanerZein Let's Win the Election (JOI22_ho_t3) C++14
16 / 100
 602 ms 2380 KB 
#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){
  dd aa=a; dd bb=b;
  swap(aa.second,aa.first); swap(bb.second,bb.first);
  return aa<bb;
}
int n;
vector<dd> st;
double ka;
double dp[510][510];
double knap(int id,int k){
  if(dp[id][k]!=-1) return dp[id][k];
  if(id==n) {
    if(k!=ka) return MAX;
    return 0;
  }
  double ans=knap(id+1,k)+st[id].first/(ka+1);
  if(k!=ka){
    ans=min(ans,knap(id+1,k+1)+st[id].second/(double)(k+1));
  }
  return dp[id][k]=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;
  n=k;
  for(int i=0;i<=k;i++){
    ka=i;
    for(int j=0;j<=n;j++) for(int l=0;l<=n;l++) dp[j][l]=-1;
    double rp=knap(0,0);
    //cout<<i<<": "<<rp<<endl;
    res=min(res,rp);
  }
  printf("%.15f\n",res);
}

Compilation message

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

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 11 ms 824 KB Output is correct
7 Correct 70 ms 1312 KB Output is correct
8 Correct 229 ms 1824 KB Output is correct
9 Correct 544 ms 2332 KB Output is correct
10 Correct 186 ms 1620 KB Output is correct

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 11 ms 824 KB Output is correct
7 Correct 70 ms 1312 KB Output is correct
8 Correct 229 ms 1824 KB Output is correct
9 Correct 544 ms 2332 KB Output is correct
10 Correct 186 ms 1620 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 16 ms 852 KB Output is correct
13 Incorrect 17 ms 928 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 568 ms 2328 KB Output is correct
2 Correct 602 ms 2260 KB Output is correct
3 Correct 533 ms 2344 KB Output is correct
4 Correct 537 ms 2332 KB Output is correct
5 Correct 557 ms 2380 KB Output is correct
6 Correct 553 ms 2328 KB Output is correct
7 Correct 536 ms 2328 KB Output is correct

Subtask #7
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 11 ms 824 KB Output is correct
7 Correct 70 ms 1312 KB Output is correct
8 Correct 229 ms 1824 KB Output is correct
9 Correct 544 ms 2332 KB Output is correct
10 Correct 186 ms 1620 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 16 ms 852 KB Output is correct
13 Incorrect 17 ms 928 KB Output isn't correct
14 Halted 0 ms 0 KB -