답안 #1106177

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1106177	2024-10-29T13:25:37 Z	akim9905	Let's Win the Election (JOI22_ho_t3)	C++17	10 / 100	1179 ms	1008788 KB

Main

#include <bits/stdc++.h>
using namespace std;

#define fileio() freopen("input.txt","r",stdin); freopen("output.txt","w",stdout)
#define fio() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) (x).begin(), (x).end()
#define allr(x) x.rbegin(), x.rend()
#define cmprs(x) sort(all(x)),x.erase(unique(all(x)),x.end())
#define endl "\n"
#define sp " "
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define F first
#define S second
#define rz resize
#define sz(a) (int)(a.size())
#define clr(a) a.clear()

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef tuple<int, int, int> tpi;
typedef tuple<ll, ll, ll> tpl;
typedef pair<double, ll> pdl;
typedef pair<double, int> pdi;

const int dx[] = {1,-1,0,0,1,1,-1,-1};
const int dy[] = {0,0,1,-1,1,-1,1,-1};
const ll MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MAX = 505; // PLZ CHK!

int N,K;
pair<double,double> A[MAX];
double D[MAX][MAX][MAX];
const double eps=1e-5;

double go(int i, int j, int k) {
    if (k==K) return 0.0;
    if (i>N) return 1e9;
    double &ret=D[i][j][k];
    if (ret>-1.0) return ret;

    ret=go(i+1,j,k);
    ret=min(ret, go(i+1,j,k+1)+A[i].first/(1.0*j));
    if (A[i].second>-1.0) ret=min(ret, go(i+1,j+1,k+1)+A[i].second/(1.0*j));

    return ret;
}

int main() {
    fio();
    cin>>N>>K;
    for (int i=1; i<=N; i++) {
        cin>>A[i].first>>A[i].second;
        if (abs(A[i].second+1.0)<eps) A[i].second=1e9;
    }

    sort(A+1,A+N+1,[](auto a, auto b){
        if (abs(a.second-b.second)<eps) return a.first<b.first;
        return a.second<b.second;
    });

    fill_n(&D[0][0][0],MAX*MAX*MAX,-1.0);

    cout<<fixed; cout.precision(10);
    cout<<go(1,1,0);
    return 0;
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	451 ms	1008788 KB	Output is correct
2	Correct	462 ms	1008432 KB	Output is correct
3	Correct	464 ms	1008456 KB	Output is correct
4	Correct	470 ms	1008456 KB	Output is correct
5	Correct	490 ms	1008456 KB	Output is correct
6	Correct	557 ms	1008456 KB	Output is correct
7	Correct	694 ms	1008504 KB	Output is correct
8	Correct	856 ms	1008512 KB	Output is correct
9	Correct	960 ms	1008620 KB	Output is correct
10	Correct	936 ms	1008524 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	451 ms	1008788 KB	Output is correct
2	Correct	462 ms	1008432 KB	Output is correct
3	Correct	464 ms	1008456 KB	Output is correct
4	Correct	470 ms	1008456 KB	Output is correct
5	Correct	490 ms	1008456 KB	Output is correct
6	Correct	557 ms	1008456 KB	Output is correct
7	Correct	694 ms	1008504 KB	Output is correct
8	Correct	856 ms	1008512 KB	Output is correct
9	Correct	960 ms	1008620 KB	Output is correct
10	Correct	936 ms	1008524 KB	Output is correct
11	Correct	478 ms	1008468 KB	Output is correct
12	Correct	570 ms	1008560 KB	Output is correct
13	Correct	555 ms	1008456 KB	Output is correct
14	Correct	565 ms	1008456 KB	Output is correct
15	Correct	918 ms	1008620 KB	Output is correct
16	Correct	871 ms	1008456 KB	Output is correct
17	Correct	864 ms	1008456 KB	Output is correct
18	Correct	969 ms	1008612 KB	Output is correct
19	Correct	1025 ms	1008456 KB	Output is correct
20	Correct	969 ms	1008452 KB	Output is correct

Subtask #3
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	436 ms	1008372 KB	Output is correct
2	Correct	425 ms	1008352 KB	Output is correct
3	Correct	422 ms	1008396 KB	Output is correct
4	Correct	471 ms	1008452 KB	Output is correct
5	Correct	476 ms	1008456 KB	Output is correct
6	Correct	483 ms	1008456 KB	Output is correct
7	Correct	503 ms	1008508 KB	Output is correct
8	Correct	527 ms	1008504 KB	Output is correct
9	Incorrect	538 ms	1008456 KB	Output isn't correct
10	Halted	0 ms	0 KB	-

Subtask #4
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	436 ms	1008372 KB	Output is correct
2	Correct	425 ms	1008352 KB	Output is correct
3	Correct	422 ms	1008396 KB	Output is correct
4	Correct	471 ms	1008452 KB	Output is correct
5	Correct	476 ms	1008456 KB	Output is correct
6	Correct	483 ms	1008456 KB	Output is correct
7	Correct	503 ms	1008508 KB	Output is correct
8	Correct	527 ms	1008504 KB	Output is correct
9	Incorrect	538 ms	1008456 KB	Output isn't correct
10	Halted	0 ms	0 KB	-

Subtask #5
0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	436 ms	1008372 KB	Output is correct
2	Correct	425 ms	1008352 KB	Output is correct
3	Correct	422 ms	1008396 KB	Output is correct
4	Correct	471 ms	1008452 KB	Output is correct
5	Correct	476 ms	1008456 KB	Output is correct
6	Correct	483 ms	1008456 KB	Output is correct
7	Correct	503 ms	1008508 KB	Output is correct
8	Correct	527 ms	1008504 KB	Output is correct
9	Incorrect	538 ms	1008456 KB	Output isn't correct
10	Halted	0 ms	0 KB	-

Subtask #6
0 / 11.0

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

Subtask #7
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	451 ms	1008788 KB	Output is correct
2	Correct	462 ms	1008432 KB	Output is correct
3	Correct	464 ms	1008456 KB	Output is correct
4	Correct	470 ms	1008456 KB	Output is correct
5	Correct	490 ms	1008456 KB	Output is correct
6	Correct	557 ms	1008456 KB	Output is correct
7	Correct	694 ms	1008504 KB	Output is correct
8	Correct	856 ms	1008512 KB	Output is correct
9	Correct	960 ms	1008620 KB	Output is correct
10	Correct	936 ms	1008524 KB	Output is correct
11	Correct	478 ms	1008468 KB	Output is correct
12	Correct	570 ms	1008560 KB	Output is correct
13	Correct	555 ms	1008456 KB	Output is correct
14	Correct	565 ms	1008456 KB	Output is correct
15	Correct	918 ms	1008620 KB	Output is correct
16	Correct	871 ms	1008456 KB	Output is correct
17	Correct	864 ms	1008456 KB	Output is correct
18	Correct	969 ms	1008612 KB	Output is correct
19	Correct	1025 ms	1008456 KB	Output is correct
20	Correct	969 ms	1008452 KB	Output is correct
21	Correct	436 ms	1008372 KB	Output is correct
22	Correct	425 ms	1008352 KB	Output is correct
23	Correct	422 ms	1008396 KB	Output is correct
24	Correct	471 ms	1008452 KB	Output is correct
25	Correct	476 ms	1008456 KB	Output is correct
26	Correct	483 ms	1008456 KB	Output is correct
27	Correct	503 ms	1008508 KB	Output is correct
28	Correct	527 ms	1008504 KB	Output is correct
29	Incorrect	538 ms	1008456 KB	Output isn't correct
30	Halted	0 ms	0 KB	-

답안 #1106177

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 5.0 / 5.0

Subtask #3 0 / 11.0

Subtask #4 0 / 12.0

Subtask #5 0 / 33.0

Subtask #6 0 / 11.0

Subtask #7 0 / 23.0

Subtask #1
5.0 / 5.0

Subtask #2
5.0 / 5.0

Subtask #3
0 / 11.0

Subtask #4
0 / 12.0

Subtask #5
0 / 33.0

Subtask #6
0 / 11.0

Subtask #7
0 / 23.0