Submission #309936

#TimeUsernameProblemLanguageResultExecution timeMemory
309936phathnv새로운 문제 (COCI19_akvizna)C++11
0 / 130
1598 ms40828 KiB
#include <bits/stdc++.h> using namespace std; #define X first #define Y second #define mp make_pair typedef long long ll; typedef pair<int, int> ii; const int N = 3001; struct line{ double a, b; int cnt; line(double _a = 0, double _b = 0, int _cnt = 0){ a = _a; b = _b; cnt = _cnt; } }; struct convexHull{ vector <line> d; int ptr; void reset(){ d.clear(); ptr = 0; } double calcY(const line &l, ll x){ return l.a * x + l.b; } bool bad(const line &l1, const line &l2, const line &l3){ return (l2.a - l3.a) * (l2.b - l1.b) >= (l1.a - l2.a) * (l3.b - l2.b); } void add(const line &newLine){ while (d.size() > 1){ if (bad(d[d.size() - 2], d[d.size() - 1], newLine)) d.pop_back(); else break; } d.push_back(newLine); } double getMax(double x){ assert(!d.empty()); ptr = min(ptr, (int) d.size() - 1); while (ptr < (int) d.size() - 1) if (calcY(d[ptr], x) <= calcY(d[ptr + 1], x)) ptr++; else break; return calcY(d[ptr], x); } int getCnt(double x){ assert(!d.empty()); ptr = min(ptr, (int) d.size() - 1); while (ptr < (int) d.size() - 1) if (calcY(d[ptr], x) <= calcY(d[ptr + 1], x)) ptr++; else break; return d[ptr].cnt; } } cvh; int n, k; double dp[N][N]; void readInput(){ cin >> n >> k; } void solve(){ dp[1][0] = 0; for(int j = 1; j <= n; j++) dp[1][j] = 1; for(int i = 2; i <= k; i++){ cvh.reset(); for(int j = 1; j <= n; j++){ cvh.add(line(dp[i - 1][j - 1], -(j - 1))); dp[i][j] = cvh.getMax(j) / j + 1; } } cout << dp[k][n]; } int main(){ readInput(); solve(); return 0; }
#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...
#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...
#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...
#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...