Submission #246553

#	Time	Username	Problem	Language	Result	Execution time	Memory
246553		BartolM	새로운 문제 (COCI19_akvizna)	C++17	65 / 130	390 ms	150520 KiB

Main

#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 (stderr)

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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 5 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5
• Subtask 22: 0 / 5
• Subtask 23: 0 / 5
• Subtask 24: 0 / 5
• Subtask 25: 0 / 5
• Subtask 26: 0 / 5