oj.uz

답안 #806075

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
806075 2023-08-04T04:37:57 Z vjudge1 Let's Win the Election (JOI22_ho_t3) C++17
0 / 100
 2500 ms 8548 KB 
#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

const int N = 500;
const ld INF = 1e16;

int n, k;
pair<ld, ld> c[N + 10];



int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n; i++) {
        cin >> c[i].first >> c[i].second;
        if(c[i].second == -1) c[i].second = INF;
    }
    sort(c + 1, c + n + 1, [](pair<ld, ld> x, pair<ld, ld> y) {return x.second < y.second;});

    // for(int i = 1; i <= n; i++) 
    //     cout << c[i].first << ' ' << c[i].second << '\n';
    // cout << '\n';
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    ld res = INF;
    for(int _ = 0; _ < 10000; _++) {
        next_permutation(order.begin(), order.end());
        pair<ld, ld> d[n + 1];
        for(int i = 1; i <= n; i++) 
            d[i] = c[order[i - 1]];
        vector<vector<ld>> dp(n + 1, vector<ld>(n + 1, INF));
        dp[0][1] = 0;
        for(int i = 1; i <= n; i++) {
            vector<vector<ld>> newdp = dp;
            for(int k = 1; k <= i; k++) {
                for(int v = 1; v <= i + 1; v++) {
                    newdp[k][v] = min(newdp[k][v], dp[k - 1][v] + c[i].first / v); 
                    if(v > 1 && c[i].second != INF) 
                        newdp[k][v] = min(newdp[k][v], dp[k - 1][v - 1] + c[i].second / (v - 1)) ;
                }
            }
            dp = newdp;
            // for(int k = 1; k <= n; k++) {
            //     for(int v = 1; v <= n; v++) {
            //         cout <<setprecision(1) << fixed << dp[k][v] << ' ';
            //     }
            //     cout << '\n';
            // }
            // cout << '\n';
        }
        for(int v = 1; v <= n; v++) {
            res = min(res, dp[k][v]);
        }
    }
    cout << setprecision(9) << fixed << res ;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 4 ms 212 KB Output is correct
3 Correct 7 ms 212 KB Output is correct
4 Correct 10 ms 212 KB Output is correct
5 Execution timed out 2581 ms 8548 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 4 ms 212 KB Output is correct
3 Correct 7 ms 212 KB Output is correct
4 Correct 10 ms 212 KB Output is correct
5 Execution timed out 2581 ms 8548 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 212 KB Output is correct
2 Correct 38 ms 316 KB Output is correct
3 Correct 36 ms 332 KB Output is correct
4 Correct 39 ms 212 KB Output is correct
5 Correct 39 ms 212 KB Output is correct
6 Correct 40 ms 308 KB Output is correct
7 Correct 50 ms 212 KB Output is correct
8 Correct 42 ms 324 KB Output is correct
9 Incorrect 40 ms 316 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 212 KB Output is correct
2 Correct 38 ms 316 KB Output is correct
3 Correct 36 ms 332 KB Output is correct
4 Correct 39 ms 212 KB Output is correct
5 Correct 39 ms 212 KB Output is correct
6 Correct 40 ms 308 KB Output is correct
7 Correct 50 ms 212 KB Output is correct
8 Correct 42 ms 324 KB Output is correct
9 Incorrect 40 ms 316 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 212 KB Output is correct
2 Correct 38 ms 316 KB Output is correct
3 Correct 36 ms 332 KB Output is correct
4 Correct 39 ms 212 KB Output is correct
5 Correct 39 ms 212 KB Output is correct
6 Correct 40 ms 308 KB Output is correct
7 Correct 50 ms 212 KB Output is correct
8 Correct 42 ms 324 KB Output is correct
9 Incorrect 40 ms 316 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2567 ms 8532 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 4 ms 212 KB Output is correct
3 Correct 7 ms 212 KB Output is correct
4 Correct 10 ms 212 KB Output is correct
5 Execution timed out 2581 ms 8548 KB Time limit exceeded
6 Halted 0 ms 0 KB -