oj.uz

답안 #465123

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
465123 2021-08-15T08:29:24 Z MahdiBahramian The short shank; Redemption (BOI21_prison) C++17
0 / 100
 457 ms 15012 KB 
#include<bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define mk make_pair
#define mt make_tuple
using namespace std;
const int Max = 2e6 + 10 , INF = 1e9 + 10;
int n , t;
int A[Max];
double dp[Max]; int last[Max] , cnt[Max];
void CALC(double tst)
{
    last[0] = INF;
    for(int i = 1 ; i <= n ; i++)
    {
        dp[i] = dp[i - 1] + tst + (A[i] <= t) , cnt[i] = cnt[i - 1] + 1 , last[i] = A[i];
        if(dp[i] > dp[i - 1] + (min(last[i - 1] + 1 , A[i]) <= t))
        {
            dp[i] = dp[i - 1] + (min(last[i - 1] + 1 , A[i]) <= t);
            cnt[i] = cnt[i - 1];
            last[i] = min(last[i - 1] + 1 , A[i]);
        }
    }
}
int main()
{
    ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
    int d; cin >> n >> d >> t;
    for(int i = 1 ; i <= n ; i++) cin >> A[i];

    double l = 1e9 , r = -1e9;
    for(int lg = 0 ; lg < 100 ; lg++)
    {
        double md = (l + r) / 2;
        CALC(md);
        if(cnt[n] >= d) r = md;
        else l = md;
    }
    CALC(r);
    cout << dp[n] - r * cnt[n];
}

Subtask #1
0 / 15.0

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

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 457 ms 15012 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 67 ms 2528 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

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

Subtask #6
0 / 20.0

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