oj.uz

Submission #780039

# Submission time Handle Problem Language Result Execution time Memory
780039 2023-07-12T05:56:50 Z 이동현(#10007) Sparklers (JOI17_sparklers) C++17
50 / 100
 75 ms 34104 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define int long long
using namespace std;

const int NS = (int)1e5 + 4;
int n, k, t;
int a[NS];
int mn[1004][1004], mx[1004][1004];

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> k >> t;
    --k;
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }
    int low = 0, high = (int)1e9, mid;
    for(int i = 0; i < 1004; ++i) for(int j = 0; j < 1004; ++j) mn[i][j] = (int)1e18, mx[i][j] = -(int)1e18;
    while(low < high){
        mid = low + high >> 1;
        mn[k][k] = a[k] - t * mid;
        mx[k][k] = a[k] + t * mid;

        for(int i = n - 1; i >= 0; --i){
            for(int j = i + 1; j < n; ++j){
                mn[i][j] = (int)1e18;
                mx[i][j] = -(int)1e18;

                int l = mn[i + 1][j], r = mx[i + 1][j];
                r = min(r, a[i] + (j - i) * t * mid);
                l = max(l, a[i] - (j - i) * t * mid);
                if(l <= r){
                    mx[i][j] = max(mx[i][j], r + t * mid);
                    mn[i][j] = min(mn[i][j], l - t * mid);
                }

                l = mn[i][j - 1], r = mx[i][j - 1];
                r = min(r, a[j] + (j - i) * t * mid);
                l = max(l, a[j] - (j - i) * t * mid);
                if(l <= r){
                    mx[i][j] = max(mx[i][j], r + t * mid);
                    mn[i][j] = min(mn[i][j], l - t * mid);
                }
            }
        }

        if(mn[0][n - 1] != (int)1e18){
            high = mid;
        }
        else{
            low = mid + 1;
        }
    }

    cout << low << '\n';

    return 0;
}

Compilation message

sparklers.cpp: In function 'int main()':
sparklers.cpp:25:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |         mid = low + high >> 1;
      |               ~~~~^~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16084 KB Output is correct
2 Correct 7 ms 16084 KB Output is correct
3 Correct 7 ms 16084 KB Output is correct
4 Correct 6 ms 16084 KB Output is correct
5 Correct 6 ms 16084 KB Output is correct
6 Correct 6 ms 16084 KB Output is correct
7 Correct 6 ms 16084 KB Output is correct
8 Correct 7 ms 16084 KB Output is correct
9 Correct 7 ms 16084 KB Output is correct
10 Correct 6 ms 16084 KB Output is correct
11 Correct 6 ms 16084 KB Output is correct
12 Correct 6 ms 16028 KB Output is correct
13 Correct 7 ms 16076 KB Output is correct
14 Correct 8 ms 16084 KB Output is correct
15 Correct 8 ms 16060 KB Output is correct
16 Correct 8 ms 16084 KB Output is correct
17 Correct 6 ms 16088 KB Output is correct
18 Correct 8 ms 16084 KB Output is correct
19 Correct 6 ms 16084 KB Output is correct
20 Correct 6 ms 16084 KB Output is correct
21 Correct 6 ms 16084 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16084 KB Output is correct
2 Correct 7 ms 16084 KB Output is correct
3 Correct 7 ms 16084 KB Output is correct
4 Correct 6 ms 16084 KB Output is correct
5 Correct 6 ms 16084 KB Output is correct
6 Correct 6 ms 16084 KB Output is correct
7 Correct 6 ms 16084 KB Output is correct
8 Correct 7 ms 16084 KB Output is correct
9 Correct 7 ms 16084 KB Output is correct
10 Correct 6 ms 16084 KB Output is correct
11 Correct 6 ms 16084 KB Output is correct
12 Correct 6 ms 16028 KB Output is correct
13 Correct 7 ms 16076 KB Output is correct
14 Correct 8 ms 16084 KB Output is correct
15 Correct 8 ms 16060 KB Output is correct
16 Correct 8 ms 16084 KB Output is correct
17 Correct 6 ms 16088 KB Output is correct
18 Correct 8 ms 16084 KB Output is correct
19 Correct 6 ms 16084 KB Output is correct
20 Correct 6 ms 16084 KB Output is correct
21 Correct 6 ms 16084 KB Output is correct
22 Correct 33 ms 16084 KB Output is correct
23 Correct 23 ms 16120 KB Output is correct
24 Correct 32 ms 16120 KB Output is correct
25 Correct 49 ms 16100 KB Output is correct
26 Correct 51 ms 16084 KB Output is correct
27 Correct 52 ms 16080 KB Output is correct
28 Correct 59 ms 16076 KB Output is correct
29 Correct 56 ms 16104 KB Output is correct
30 Correct 53 ms 16104 KB Output is correct
31 Correct 56 ms 16084 KB Output is correct
32 Correct 55 ms 16084 KB Output is correct
33 Correct 60 ms 16084 KB Output is correct
34 Correct 53 ms 16080 KB Output is correct
35 Correct 56 ms 16104 KB Output is correct
36 Correct 49 ms 16084 KB Output is correct
37 Correct 48 ms 16084 KB Output is correct
38 Correct 57 ms 16084 KB Output is correct
39 Correct 48 ms 16108 KB Output is correct
40 Correct 75 ms 16084 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16084 KB Output is correct
2 Correct 7 ms 16084 KB Output is correct
3 Correct 7 ms 16084 KB Output is correct
4 Correct 6 ms 16084 KB Output is correct
5 Correct 6 ms 16084 KB Output is correct
6 Correct 6 ms 16084 KB Output is correct
7 Correct 6 ms 16084 KB Output is correct
8 Correct 7 ms 16084 KB Output is correct
9 Correct 7 ms 16084 KB Output is correct
10 Correct 6 ms 16084 KB Output is correct
11 Correct 6 ms 16084 KB Output is correct
12 Correct 6 ms 16028 KB Output is correct
13 Correct 7 ms 16076 KB Output is correct
14 Correct 8 ms 16084 KB Output is correct
15 Correct 8 ms 16060 KB Output is correct
16 Correct 8 ms 16084 KB Output is correct
17 Correct 6 ms 16088 KB Output is correct
18 Correct 8 ms 16084 KB Output is correct
19 Correct 6 ms 16084 KB Output is correct
20 Correct 6 ms 16084 KB Output is correct
21 Correct 6 ms 16084 KB Output is correct
22 Correct 33 ms 16084 KB Output is correct
23 Correct 23 ms 16120 KB Output is correct
24 Correct 32 ms 16120 KB Output is correct
25 Correct 49 ms 16100 KB Output is correct
26 Correct 51 ms 16084 KB Output is correct
27 Correct 52 ms 16080 KB Output is correct
28 Correct 59 ms 16076 KB Output is correct
29 Correct 56 ms 16104 KB Output is correct
30 Correct 53 ms 16104 KB Output is correct
31 Correct 56 ms 16084 KB Output is correct
32 Correct 55 ms 16084 KB Output is correct
33 Correct 60 ms 16084 KB Output is correct
34 Correct 53 ms 16080 KB Output is correct
35 Correct 56 ms 16104 KB Output is correct
36 Correct 49 ms 16084 KB Output is correct
37 Correct 48 ms 16084 KB Output is correct
38 Correct 57 ms 16084 KB Output is correct
39 Correct 48 ms 16108 KB Output is correct
40 Correct 75 ms 16084 KB Output is correct
41 Runtime error 25 ms 34104 KB Execution killed with signal 11
42 Halted 0 ms 0 KB -