답안 #1106187

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1106187	2024-10-29T13:32:17 Z	akim9905	Let's Win the Election (JOI22_ho_t3)	C++17	10 / 100	1069 ms	1008708 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<1e9) 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	500 ms	1008388 KB	Output is correct
2	Correct	448 ms	1008456 KB	Output is correct
3	Correct	463 ms	1008380 KB	Output is correct
4	Correct	470 ms	1008456 KB	Output is correct
5	Correct	481 ms	1008456 KB	Output is correct
6	Correct	487 ms	1008620 KB	Output is correct
7	Correct	469 ms	1008552 KB	Output is correct
8	Correct	466 ms	1008432 KB	Output is correct
9	Correct	420 ms	1008456 KB	Output is correct
10	Correct	430 ms	1008552 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	500 ms	1008388 KB	Output is correct
2	Correct	448 ms	1008456 KB	Output is correct
3	Correct	463 ms	1008380 KB	Output is correct
4	Correct	470 ms	1008456 KB	Output is correct
5	Correct	481 ms	1008456 KB	Output is correct
6	Correct	487 ms	1008620 KB	Output is correct
7	Correct	469 ms	1008552 KB	Output is correct
8	Correct	466 ms	1008432 KB	Output is correct
9	Correct	420 ms	1008456 KB	Output is correct
10	Correct	430 ms	1008552 KB	Output is correct
11	Correct	429 ms	1008552 KB	Output is correct
12	Correct	565 ms	1008456 KB	Output is correct
13	Correct	525 ms	1008456 KB	Output is correct
14	Correct	522 ms	1008456 KB	Output is correct
15	Correct	945 ms	1008624 KB	Output is correct
16	Correct	832 ms	1008392 KB	Output is correct
17	Correct	629 ms	1008400 KB	Output is correct
18	Correct	1069 ms	1008456 KB	Output is correct
19	Correct	837 ms	1008624 KB	Output is correct
20	Correct	589 ms	1008456 KB	Output is correct

Subtask #3
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	497 ms	1008456 KB	Output is correct
2	Correct	502 ms	1008456 KB	Output is correct
3	Correct	502 ms	1008500 KB	Output is correct
4	Correct	496 ms	1008372 KB	Output is correct
5	Correct	453 ms	1008412 KB	Output is correct
6	Correct	435 ms	1008332 KB	Output is correct
7	Correct	438 ms	1008708 KB	Output is correct
8	Correct	433 ms	1008456 KB	Output is correct
9	Incorrect	450 ms	1008456 KB	Output isn't correct
10	Halted	0 ms	0 KB	-

Subtask #4
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	497 ms	1008456 KB	Output is correct
2	Correct	502 ms	1008456 KB	Output is correct
3	Correct	502 ms	1008500 KB	Output is correct
4	Correct	496 ms	1008372 KB	Output is correct
5	Correct	453 ms	1008412 KB	Output is correct
6	Correct	435 ms	1008332 KB	Output is correct
7	Correct	438 ms	1008708 KB	Output is correct
8	Correct	433 ms	1008456 KB	Output is correct
9	Incorrect	450 ms	1008456 KB	Output isn't correct
10	Halted	0 ms	0 KB	-

Subtask #5
0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	497 ms	1008456 KB	Output is correct
2	Correct	502 ms	1008456 KB	Output is correct
3	Correct	502 ms	1008500 KB	Output is correct
4	Correct	496 ms	1008372 KB	Output is correct
5	Correct	453 ms	1008412 KB	Output is correct
6	Correct	435 ms	1008332 KB	Output is correct
7	Correct	438 ms	1008708 KB	Output is correct
8	Correct	433 ms	1008456 KB	Output is correct
9	Incorrect	450 ms	1008456 KB	Output isn't correct
10	Halted	0 ms	0 KB	-

Subtask #6
0 / 11.0

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

Subtask #7
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	500 ms	1008388 KB	Output is correct
2	Correct	448 ms	1008456 KB	Output is correct
3	Correct	463 ms	1008380 KB	Output is correct
4	Correct	470 ms	1008456 KB	Output is correct
5	Correct	481 ms	1008456 KB	Output is correct
6	Correct	487 ms	1008620 KB	Output is correct
7	Correct	469 ms	1008552 KB	Output is correct
8	Correct	466 ms	1008432 KB	Output is correct
9	Correct	420 ms	1008456 KB	Output is correct
10	Correct	430 ms	1008552 KB	Output is correct
11	Correct	429 ms	1008552 KB	Output is correct
12	Correct	565 ms	1008456 KB	Output is correct
13	Correct	525 ms	1008456 KB	Output is correct
14	Correct	522 ms	1008456 KB	Output is correct
15	Correct	945 ms	1008624 KB	Output is correct
16	Correct	832 ms	1008392 KB	Output is correct
17	Correct	629 ms	1008400 KB	Output is correct
18	Correct	1069 ms	1008456 KB	Output is correct
19	Correct	837 ms	1008624 KB	Output is correct
20	Correct	589 ms	1008456 KB	Output is correct
21	Correct	497 ms	1008456 KB	Output is correct
22	Correct	502 ms	1008456 KB	Output is correct
23	Correct	502 ms	1008500 KB	Output is correct
24	Correct	496 ms	1008372 KB	Output is correct
25	Correct	453 ms	1008412 KB	Output is correct
26	Correct	435 ms	1008332 KB	Output is correct
27	Correct	438 ms	1008708 KB	Output is correct
28	Correct	433 ms	1008456 KB	Output is correct
29	Incorrect	450 ms	1008456 KB	Output isn't correct
30	Halted	0 ms	0 KB	-

답안 #1106187

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