oj.uz

답안 #580459

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
580459 2022-06-21T09:21:10 Z 반딧불(#8355) Uplifting Excursion (BOI22_vault) C++17
10 / 100
 3676 ms 78668 KB 
#include <bits/stdc++.h>
#ifndef TEST
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#endif

using namespace std;

typedef long long ll;
const ll LIM = 1000000;

void imp(){
    puts("impossible");
    exit(0);
}

ll dq1[2000002];
ll dq2[2000002];
int fr, sz;

ll f(ll x, ll y, bool b){
    if(b) return max(x, y);
    return min(x, y);
}

void calculateMax(int n, ll* arr, int lim, vector<ll>& ret){
    ret = vector<ll>(lim*2+1, -1e18);
    ret[lim] = 0;
    vector<ll> tvec (lim*2+1, -1e18);
    for(int ri=0; ri<=n+n; ri++){
        tvec.swap(ret);
        if(ri>n){
            int i = ri-n;
            for(int s=0; s<i; s++){
                fr=sz=0;
                for(int j=s, p=0; j<=lim*2; j+=i, p++){
                    ret[j] = max(ret[j], tvec[j]);
                    while(fr!=sz && dq2[fr] < p) fr++;
                    ll nf = tvec[j]-p;
                    while(fr!=sz && dq1[sz-1] < nf) sz--;
                    dq1[sz] = nf;
                    dq2[sz++] = p+arr[ri];
                    ret[j] = max(ret[j], dq1[fr] + p);
                }
            }
        }
        else if(ri<n){
            int i = n-ri;
            for(int s=0; s<i; s++){
                fr=sz=0;
                for(int j=lim*2-s, p=0; j>=0; j-=i, p++){
                    ret[j] = max(ret[j], tvec[j]);
                    while(fr!=sz && dq2[fr] < p) fr++;
                    ll nf = tvec[j]-p;
                    while(fr!=sz && dq1[sz-1] < nf) sz--;
                    dq1[sz] = nf;
                    dq2[sz++] = p+arr[ri];
                    ret[j] = max(ret[j], dq1[fr] + p);
                }
            }
        }
        else tvec.swap(ret);
    }
}

void calculateMin(int n, ll* arr, int lim, vector<ll>& ret){
    ret = vector<ll>(lim*2+1, 1e18);
    ret[lim] = 0;
    vector<ll> tvec (lim*2+1, 1e18);
    for(int ri=0; ri<=n+n; ri++){
        tvec.swap(ret);
        if(ri>n){
            int i = ri-n;
            for(int s=0; s<i; s++){
                fr=sz=0;
                for(int j=s, p=0; j<=lim*2; j+=i, p++){
                    ret[j] = min(ret[j], tvec[j]);
                    while(fr!=sz && dq2[fr] < p) fr++;
                    ll nf = tvec[j]-p;
                    while(fr!=sz && dq1[sz-1] > nf) sz--;
                    dq1[sz] = nf;
                    dq2[sz++] = p+arr[ri];
                    ret[j] = min(ret[j], dq1[fr] + p);
                }
            }
        }
        else if(ri<n){
            int i = n-ri;
            for(int s=0; s<i; s++){
                fr=sz=0;
                for(int j=lim*2-s, p=0; j>=0; j-=i, p++){
                    ret[j] = min(ret[j], tvec[j]);
                    while(fr!=sz && dq2[fr] < p) fr++;
                    ll nf = tvec[j]-p;
                    while(fr!=sz && dq1[sz-1] > nf) sz--;
                    dq1[sz] = nf;
                    dq2[sz++] = p+arr[ri];
                    ret[j] = min(ret[j], dq1[fr] + p);
                }
            }
        }
        else tvec.swap(ret);
    }
}

int n;
ll k;
ll arr[702];

ll used[702];
ll rem[702];
vector<ll> DP, DP2;

ll ans = -1e18;
ll frontCnt;

int main(){
    scanf("%lld %lld", &n, &k);
    if(n>30) return 1;
    for(int i=0; i<=n+n; i++){
        scanf("%lld", &arr[i]);
//        arr[i] = ll(rand()) * ll(rand()) * ll(rand()) * ll(rand()) % 100LL;
    }
//    printf("%lld\n", arr[1] + min(arr[0], arr[2])*2);
    if(k<0){
        k*=-1;
        reverse(arr, arr+n+n+1);
    }

    for(int i=0; i<=n+n; i++) used[i] = 0, rem[i] = arr[i];
    for(int i=n; i<=n+n; i++){
        if(k >= arr[i]*(i-n)){
            k -= arr[i]*(i-n);
            used[i] = arr[i];
            rem[i] = 0;
        }
        else{
            ll tmp = k/(i-n);
            used[i] = tmp;
            rem[i] = arr[i]-tmp;
            k -= tmp*(i-n);
        }
    }
    if(accumulate(rem, rem+n+n+1, 0LL) == 0 && k) imp();
    for(int i=1; i<=n; i++){
        ll tmp = min(rem[n-i], rem[n+i]);
        rem[n-i] -= tmp, rem[n+i] -= tmp;
        used[n-i] += tmp, used[n+i] += tmp;
    }
    frontCnt = accumulate(used, used+n+n+1, 0LL);

    calculateMax(n, rem, LIM, DP); /// �ִ�
    calculateMin(n, used, LIM, DP2); /// �ּ�

    for(ll i=0; i<=LIM+LIM; i++){
        ll j = (i-LIM)-k+LIM;
        if(0<=j && j<=LIM+LIM) ans = max(ans, frontCnt + DP[i] - DP2[j]);
    }

    if(ans <= 0) imp();
    printf("%lld", ans);
}

Compilation message

vault.cpp: In function 'int main()':
vault.cpp:119:15: warning: format '%lld' expects argument of type 'long long int*', but argument 2 has type 'int*' [-Wformat=]
  119 |     scanf("%lld %lld", &n, &k);
      |            ~~~^        ~~
      |               |        |
      |               |        int*
      |               long long int*
      |            %d
vault.cpp:119:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |     scanf("%lld %lld", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
vault.cpp:122:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |         scanf("%lld", &arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 78508 KB Output is correct
2 Correct 133 ms 78588 KB Output is correct
3 Correct 67 ms 78580 KB Output is correct
4 Correct 674 ms 78636 KB Output is correct
5 Runtime error 0 ms 212 KB Execution failed because the return code was nonzero
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 78508 KB Output is correct
2 Correct 133 ms 78588 KB Output is correct
3 Correct 67 ms 78580 KB Output is correct
4 Correct 674 ms 78636 KB Output is correct
5 Runtime error 0 ms 212 KB Execution failed because the return code was nonzero
6 Halted 0 ms 0 KB -

Subtask #3-1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 675 ms 78540 KB Output is correct
2 Correct 3478 ms 78520 KB Output is correct
3 Correct 3465 ms 78528 KB Output is correct
4 Correct 3380 ms 78532 KB Output is correct
5 Correct 3368 ms 78532 KB Output is correct
6 Correct 3318 ms 78612 KB Output is correct
7 Correct 3431 ms 78500 KB Output is correct
8 Correct 3347 ms 78536 KB Output is correct
9 Correct 3250 ms 78584 KB Output is correct
10 Correct 3365 ms 78540 KB Output is correct

Subtask #3-2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 675 ms 78540 KB Output is correct
2 Correct 3478 ms 78520 KB Output is correct
3 Correct 3465 ms 78528 KB Output is correct
4 Correct 3380 ms 78532 KB Output is correct
5 Correct 3368 ms 78532 KB Output is correct
6 Correct 3318 ms 78612 KB Output is correct
7 Correct 3431 ms 78500 KB Output is correct
8 Correct 3347 ms 78536 KB Output is correct
9 Correct 3250 ms 78584 KB Output is correct
10 Correct 3365 ms 78540 KB Output is correct
11 Correct 127 ms 78612 KB Output is correct
12 Correct 137 ms 78528 KB Output is correct
13 Correct 66 ms 78604 KB Output is correct
14 Correct 708 ms 78656 KB Output is correct
15 Correct 3397 ms 78660 KB Output is correct
16 Correct 3327 ms 78600 KB Output is correct
17 Correct 3605 ms 78564 KB Output is correct
18 Correct 3368 ms 78540 KB Output is correct
19 Correct 3409 ms 78536 KB Output is correct
20 Correct 3475 ms 78536 KB Output is correct
21 Correct 3492 ms 78532 KB Output is correct
22 Correct 3486 ms 78616 KB Output is correct
23 Correct 3676 ms 78604 KB Output is correct
24 Incorrect 3580 ms 78576 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 675 ms 78540 KB Output is correct
2 Correct 3478 ms 78520 KB Output is correct
3 Correct 3465 ms 78528 KB Output is correct
4 Correct 3380 ms 78532 KB Output is correct
5 Correct 3368 ms 78532 KB Output is correct
6 Correct 3318 ms 78612 KB Output is correct
7 Correct 3431 ms 78500 KB Output is correct
8 Correct 3347 ms 78536 KB Output is correct
9 Correct 3250 ms 78584 KB Output is correct
10 Correct 3365 ms 78540 KB Output is correct
11 Correct 700 ms 78540 KB Output is correct
12 Correct 3422 ms 78540 KB Output is correct
13 Correct 3470 ms 78540 KB Output is correct
14 Correct 3621 ms 78536 KB Output is correct
15 Correct 3433 ms 78668 KB Output is correct
16 Correct 3280 ms 78492 KB Output is correct
17 Correct 3400 ms 78532 KB Output is correct
18 Correct 3261 ms 78536 KB Output is correct
19 Correct 3340 ms 78616 KB Output is correct
20 Correct 3281 ms 78536 KB Output is correct
21 Runtime error 0 ms 212 KB Execution failed because the return code was nonzero
22 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 78508 KB Output is correct
2 Correct 133 ms 78588 KB Output is correct
3 Correct 67 ms 78580 KB Output is correct
4 Correct 674 ms 78636 KB Output is correct
5 Runtime error 0 ms 212 KB Execution failed because the return code was nonzero
6 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 675 ms 78540 KB Output is correct
2 Correct 3478 ms 78520 KB Output is correct
3 Correct 3465 ms 78528 KB Output is correct
4 Correct 3380 ms 78532 KB Output is correct
5 Correct 3368 ms 78532 KB Output is correct
6 Correct 3318 ms 78612 KB Output is correct
7 Correct 3431 ms 78500 KB Output is correct
8 Correct 3347 ms 78536 KB Output is correct
9 Correct 3250 ms 78584 KB Output is correct
10 Correct 3365 ms 78540 KB Output is correct
11 Correct 700 ms 78540 KB Output is correct
12 Correct 3422 ms 78540 KB Output is correct
13 Correct 3470 ms 78540 KB Output is correct
14 Correct 3621 ms 78536 KB Output is correct
15 Correct 3433 ms 78668 KB Output is correct
16 Correct 3280 ms 78492 KB Output is correct
17 Correct 3400 ms 78532 KB Output is correct
18 Correct 3261 ms 78536 KB Output is correct
19 Correct 3340 ms 78616 KB Output is correct
20 Correct 3281 ms 78536 KB Output is correct
21 Runtime error 0 ms 212 KB Execution failed because the return code was nonzero
22 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 78508 KB Output is correct
2 Correct 133 ms 78588 KB Output is correct
3 Correct 67 ms 78580 KB Output is correct
4 Correct 674 ms 78636 KB Output is correct
5 Runtime error 0 ms 212 KB Execution failed because the return code was nonzero
6 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 675 ms 78540 KB Output is correct
2 Correct 3478 ms 78520 KB Output is correct
3 Correct 3465 ms 78528 KB Output is correct
4 Correct 3380 ms 78532 KB Output is correct
5 Correct 3368 ms 78532 KB Output is correct
6 Correct 3318 ms 78612 KB Output is correct
7 Correct 3431 ms 78500 KB Output is correct
8 Correct 3347 ms 78536 KB Output is correct
9 Correct 3250 ms 78584 KB Output is correct
10 Correct 3365 ms 78540 KB Output is correct
11 Correct 700 ms 78540 KB Output is correct
12 Correct 3422 ms 78540 KB Output is correct
13 Correct 3470 ms 78540 KB Output is correct
14 Correct 3621 ms 78536 KB Output is correct
15 Correct 3433 ms 78668 KB Output is correct
16 Correct 3280 ms 78492 KB Output is correct
17 Correct 3400 ms 78532 KB Output is correct
18 Correct 3261 ms 78536 KB Output is correct
19 Correct 3340 ms 78616 KB Output is correct
20 Correct 3281 ms 78536 KB Output is correct
21 Runtime error 0 ms 212 KB Execution failed because the return code was nonzero
22 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 78508 KB Output is correct
2 Correct 133 ms 78588 KB Output is correct
3 Correct 67 ms 78580 KB Output is correct
4 Correct 674 ms 78636 KB Output is correct
5 Runtime error 0 ms 212 KB Execution failed because the return code was nonzero
6 Halted 0 ms 0 KB -