oj.uz

Submission #428862

# Submission time Handle Problem Language Result Execution time Memory
428862 2021-06-15T15:01:26 Z tqbfjotld Sparklers (JOI17_sparklers) C++14
30 / 100
 2000 ms 9948 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

map<pair<int,int>,pair<int,int> > memo;
int arr[100005];

int K,T,N;
int M;

pair<int,int> func(int a, int b){
    if (a==b) return a==K?make_pair(arr[K]-M*T,arr[K]+M*T):make_pair(999999999999999999LL,-999999999999999999LL);
    if (memo.count({a,b})) return memo[{a,b}];
   // printf("%lld %lld, %lld\n",a,b,K);
    if (b<K || a>K) return {999999999999999999LL,-999999999999999999LL};
    auto opt1 = func(a,b-1);
    auto opt2 = func(a+1,b);
   //if (opt1.first<0) opt1.first = 0;
    //if (opt2.first<0) opt2.first = 0;

       // printf("opt1 = %lld %lld, \n",opt1);
       // printf("optw = %lld %lld, ab = %lld %lld\n",opt2,a,b);
    if (opt1.second<opt1.first){
        if (opt2.second<opt2.first) return memo[{a,b}] = {999999999999999999LL,-999999999999999999LL};
        int sz = (b-a);
        if (sz*T*M+arr[a]<opt2.first) return memo[{a,b}] = {999999999999999999LL,-999999999999999999LL};
        return memo[{a,b}] = {opt2.first-T*M,(sz+1)*T*M+arr[a]};
    }
    else {
            int sz = (b-a);
            if (-sz*T*M+arr[b]>opt1.second) return memo[{a,b}] = {999999999999999999LL,-999999999999999999LL};
            return memo[{a,b}] = {-(sz+1)*T*M+arr[b],opt1.second+T*M};

    }
}

bool test(int val){
    M = val;
    memo.clear();
    auto res = func(0,N-1);
    //printf("val = %lld, res = %lld %lld\n",val,res);
    return res.second>=res.first;
}

main(){
    long long n,k,t;
    scanf("%lld%lld%lld",&n,&k,&t);
    N = n; K = k; T = t;
    K--;
    for (int x = 0; x<N; x++){
        long long t;
        scanf("%lld",&t);
        arr[x] = t;
    }
    long long r = 1000000000LL/T+1;
    int l = -1LL;
    while (l+1<r){
        int mid = (l+r)/2;
        if (test(mid)){
            r = mid;
        }
        else l = mid;
    }
    printf("%lld\n",r);
}

Compilation message

sparklers.cpp:45:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   45 | main(){
      | ^~~~
sparklers.cpp: In function 'int main()':
sparklers.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     scanf("%lld%lld%lld",&n,&k,&t);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sparklers.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         scanf("%lld",&t);
      |         ~~~~~^~~~~~~~~~~

Subtask #1
30.0 / 30.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 252 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Execution timed out 2079 ms 9948 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 252 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Execution timed out 2079 ms 9948 KB Time limit exceeded
23 Halted 0 ms 0 KB -