oj.uz

Submission #581727

# Submission time Handle Problem Language Result Execution time Memory
581727 2022-06-23T05:10:27 Z 반딧불(#8365) Sparklers (JOI17_sparklers) C++17
0 / 100
 1 ms 316 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, k;
ll t;
ll arr[100002];
pair<ll, ll> DP[1002][1002];

ll able(ll speed){
    speed*=t;
    for(int i=1; i<=n; i++) for(int j=i+1; j<=n; j++) DP[i][j].first=1e18, DP[i][j].second=-1e18;
    for(int i=1; i<=n; i++) DP[i][i] = make_pair(arr[i], arr[i]);
    for(int d=1; d<n; d++){
        for(int i=1; i+d<=n; i++){
            int j = i+d;
            if((arr[j]-speed*d) <= (DP[i][j-1].second+speed)){
                DP[i][j].first = min(DP[i][j].first, max(arr[j]-speed*d, DP[i][j-1].first-speed));
                DP[i][j].second = max(DP[i][j].second, DP[i][j-1].second+speed);
            }
            if((arr[i]+speed*d) >= (DP[i+1][j].first-speed)){
                DP[i][j].first = min(DP[i][j].first, DP[i+1][j].first-speed);
                DP[i][j].second = max(DP[i][j].second, min(arr[i]+speed*d, DP[i+1][j].second+speed));
            }
        }
    }
    return DP[1][n].first <= DP[1][n].second;
}

int main(){
    scanf("%d %d %lld", &n, &k, &t);
    for(int i=1; i<=n; i++) scanf("%lld", &arr[i]);
    if(arr[1] == arr[n]){
        puts("0");
        return 0;
    }

    ll L = 1, R = 1e9, ANS = 1e9;
    while(L<=R){
        ll MID = (L+R)/2;
        if(able(MID)) ANS = MID, R = MID-1;
        else L = MID+1;
    }
    printf("%lld", ANS);
}

Compilation message

sparklers.cpp: In function 'int main()':
sparklers.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     scanf("%d %d %lld", &n, &k, &t);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sparklers.cpp:34:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     for(int i=1; i<=n; i++) scanf("%lld", &arr[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 316 KB Output is correct
4 Incorrect 1 ms 308 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 316 KB Output is correct
4 Incorrect 1 ms 308 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 316 KB Output is correct
4 Incorrect 1 ms 308 KB Output isn't correct
5 Halted 0 ms 0 KB -