Submission #858209

#TimeUsernameProblemLanguageResultExecution timeMemory
858209BrekLet's Win the Election (JOI22_ho_t3)C++14
16 / 100
2596 ms7432 KiB
#include <bits/stdc++.h> using namespace std; long double dp[509][509]; int best[509][509]; long double zni[509][509]; pair<long double, long double> t[509]; pair<pair<long double, long double>, int> t2[509]; int rel[509]; long double w; int n, k; bool cmp(pair<long double, long double> a, pair<long double, long double> b){ return a.second < b.second; } bool cmp2(pair<pair<long double, long double>, int> a, pair<pair<long double, long double>, int> b){ return a.first.second < b.first.second; } long double reszta(int x, int lv, int a){ long double czas = 0; vector<int> v; if(a != 0){ int lv2 = lv - 1; v.push_back(rel[x]); v.push_back(rel[a]); x = best[a][lv2]; lv2--; while(x > 0 && dp[x][lv2] != 0){ v.push_back(rel[x]); x = best[x][lv2]; lv2--; } } else{ v.push_back(rel[x]); } //cout<<"besty : "; //for(int d: v) cout<<d<<" "; //cout<<endl; sort(v.begin(), v.end()); int akt = 0, pot = k - lv; bool fin = false; if(v.size() == 0) fin = true; long double moc = lv + 1; for(int o = 1; o <= n; o++){ if(pot <= 0){ break; } if(!fin && o == v[akt]){ akt++; if(akt >= (int)v.size()) fin = true; } else{ //cout<<"dod : "<<t2[o].first.first<<" "<<o<<" "<<akt<<endl; czas += (long double)(t2[o].first.first / moc); pot--; } } return czas; } long double zal(int a, int b, int lv){ long double czas = (long double)(dp[a][lv - 1] + (long double)(t[b].second / (long double)(lv))); //cout<<a<<" "<<b<<" "<<lv<<" "<<czas<<endl; if(czas >= 100000000000000000.0) return czas; return czas + reszta(b, lv, a); } int main(){ ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0); cin>>n>>k; for(int i = 1; i <= n; i++){ cin>>t[i].first>>t[i].second; if(t[i].second == -1) t[i].second = 1000000000000000120; t2[i].first = t[i]; } sort(t2 + 1, t2 + n + 1, cmp2); for(int i = 1; i <= n; i++){ t2[i].second = i; } sort(t2 + 1, t2 + n + 1); for(int i = 1; i <= n; i++){ rel[t2[i].second] = i; } long double s = 0; for(int i = 1; i <= k; i++){ //cout<<t2[i].first.first<<" "<<t2[i].first.second<<endl; s += t2[i].first.first; } // ssooooooooooooooooooooooort // rozwaz -11111 // owalamy wiecej niz k sort(t + 1, t + n + 1, cmp); //for(int i = 1; i <= n; i++){ // cout<<rel[i]<<" "; //} w = s; for(int i = 0; i <= n; i++){ dp[0][i] = 1000000000000000010; } for(int i = 1; i <= n; i++){ long double x = reszta(i, 1, 0) + (long double)(t[i].second); //cout<<"starter : "<<i<<" "<<x<<endl; w = min(w, x); dp[i][1] = t[i].second; } for(int i = 2; i <= k; i++){ for(int j = 1; j <= n; j++){ //if(j == 1) cout<<endl<<endl<<"NOW"<<endl; long double mini = 1000000000000000000; int kt = 0; for(int o = 1; o < j; o++){ long double x = zal(o, j, i); //cout<<o<<" "<<j<<" "<<i<<" "<<x<<endl; w = min(w, x); if(x < mini){ mini = x; kt = o; } } best[j][i] = kt; dp[j][i] = (long double)(dp[kt][i - 1] + (long double)(t[j].second / (long double)(i))); } } cout<<w<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...