oj.uz

Submission #246553

# Submission time Handle Problem Language Result Execution time Memory
246553 2020-07-09T15:00:54 Z BartolM Akvizna (COCI19_akvizna) C++17
65 / 130
 390 ms 150520 KB 
#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <double, double> pdd;

const int INF=0x3f3f3f3f;
const int N=3005;

int n, k;
vector <pdd> hull[N];
int ind[N];

double ccw(pdd a, pdd b, pdd c) {
    return a.X*(b.Y-c.Y)+b.X*(c.Y-a.Y)+c.X*(a.Y-b.Y);
}

double f(pdd pp, double x) {
    return pp.X*x+pp.Y;
}

void dodaj(int i, pdd pp) {
    while (hull[i].size()>1 && ccw(hull[i][(int)hull[i].size()-2], hull[i].back(), pp)>=0) hull[i].pop_back();
    hull[i].pb(pp);
    ind[i]=min(ind[i], (int)hull[i].size()-1);
}

double query(int i, double x) {
    while (ind[i]<(int)hull[i].size()-1 && f(hull[i][ind[i]], x)<f(hull[i][ind[i]+1], x)) ++ind[i];
    return f(hull[i][ind[i]], x);
}

int main() {
    scanf("%d %d", &n, &k);
    for (int i=0; i<=k; ++i) hull[i].pb(mp(1/(double)n, 0));
    double sol=-1;
    for (int i=1; i<=n; ++i) {
        for (int j=k; j>=1; --j) {
            double curr=query(j-1, i);
            dodaj(j, mp(1.0/(double)(n-i), curr-(double)i/(n-i)));
            if (i==n && j==k) sol=curr;
//            printf("i: %d, j: %d, dp: %.7f\n", i, j, curr);
        }
    }
    printf("%.10f\n", sol);
    return 0;
}

Compilation message

akvizna.cpp: In function 'int main()':
akvizna.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &k);
     ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 23672 KB Output is correct
2 Correct 259 ms 90316 KB Output is correct
3 Correct 301 ms 125432 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 31352 KB Output is correct
2 Correct 182 ms 78456 KB Output is correct
3 Correct 343 ms 135516 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 25336 KB Output is correct
2 Correct 115 ms 57128 KB Output is correct
3 Correct 314 ms 132856 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 32248 KB Output is correct
2 Correct 172 ms 72696 KB Output is correct
3 Correct 347 ms 137072 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 21752 KB Output is correct
2 Correct 183 ms 71288 KB Output is correct
3 Correct 294 ms 118236 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 22264 KB Output is correct
2 Correct 252 ms 99032 KB Output is correct
3 Correct 343 ms 136528 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 20088 KB Output is correct
2 Correct 262 ms 99448 KB Output is correct
3 Correct 390 ms 150520 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 20088 KB Output is correct
2 Correct 243 ms 73592 KB Output is correct
3 Correct 334 ms 130936 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 29304 KB Output is correct
2 Correct 203 ms 84088 KB Output is correct
3 Correct 332 ms 135876 KB Output is correct

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #22
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 724 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #23
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #24
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #25
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #26
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -