oj.uz

답안 #580450

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
580450 2022-06-21T09:12:57 Z 조영욱(#8357) Uplifting Excursion (BOI22_vault) C++17
20 / 100
 3373 ms 8120 KB 
#include <bits/stdc++.h>
using namespace std;

int m;
long long l;
int dp0[1000001];
int dp[1000001];
const int zero=500000;
long long arr[202];
typedef pair<int,int> P;

int main(void) {
    scanf("%d %lld",&m,&l);
    if (l>zero||l<-zero) {
        printf("impossible");
        return 0;
    }
    for(int i=1;i<=m*2+1;i++) {
        scanf("%lld",&arr[i]);
    }
    long long total=l;
    for(int i=m+2;i<=m*2+1;i++) {
        long long use=total/(i-m-1);
        use=min(use,arr[i]);
        total-=1LL*use*(i-m-1);
        use=max(use-100,0LL);
        arr[i]-=use;
        l-=1LL*use*(i-m-1);
        if (arr[i]>100) {
            arr[i]=100;
        }
    }
    for(int i=0;i<=zero*2;i++) {
        dp0[i]=-1e7;
        dp[i]=-1e7;
    }
    dp[zero]=0;
    for(int i=1;i<=m*2+1;i++) {
        if (i==m+1){
            for(int j=0;j<=zero*2;j++) {
                dp[j]=dp[j]+arr[m+1];
            }
            continue;
        }
        int val=abs(i-m-1);
        if (i<m+1) {
            for(int j=zero*2;j>zero*2-val;j--) {
                deque<P> dq;
                for(int k=j;k>=0;k-=val) {
                    int now=dp[k]+k/val;
                    while (!dq.empty()&&dq.back().second>k+arr[i]*val) {
                        dq.pop_back();
                    }
                    while (!dq.empty()&&dq.front().first<=now) {
                        dq.pop_front();
                    }
                    dq.push_front(P(now,k));
                    dp0[k]=max(dp0[k],dq.back().first-k/val);
                }
            }
        }
        else {
            for(int j=0;j<val;j++) {
                deque<P> dq;
                for(int k=j;k<=zero*2;k+=val) {
                    int now=dp[k]-k/val;
                    while (!dq.empty()&&dq.back().second<k-arr[i]*val) {
                        dq.pop_back();
                    }
                    while (!dq.empty()&&dq.front().first<=now) {
                        dq.pop_front();
                    }
                    dq.push_front(P(now,k));
                    dp0[k]=max(dp0[k],dq.back().first+k/val);
                }
            }
        }
        for(int j=0;j<=zero*2;j++) {
            dp[j]=dp0[j];
            dp0[j]=-1e7;
        }
    }
    if (dp[zero+l]<0) {
        printf("impossible");
        return 0;
    }
    printf("%d",dp[zero+l]);
}

Compilation message

vault.cpp: In function 'int main()':
vault.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     scanf("%d %lld",&m,&l);
      |     ~~~~~^~~~~~~~~~~~~~~~~
vault.cpp:19:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         scanf("%lld",&arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 8020 KB Output is correct
2 Correct 99 ms 8112 KB Output is correct
3 Correct 34 ms 8020 KB Output is correct
4 Correct 289 ms 8104 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1418 ms 8120 KB Output is correct
7 Correct 1546 ms 8108 KB Output is correct
8 Correct 1506 ms 8108 KB Output is correct
9 Correct 1572 ms 8112 KB Output is correct
10 Correct 1557 ms 8108 KB Output is correct
11 Correct 1601 ms 8020 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 8020 KB Output is correct
2 Correct 99 ms 8112 KB Output is correct
3 Correct 34 ms 8020 KB Output is correct
4 Correct 289 ms 8104 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1418 ms 8120 KB Output is correct
7 Correct 1546 ms 8108 KB Output is correct
8 Correct 1506 ms 8108 KB Output is correct
9 Correct 1572 ms 8112 KB Output is correct
10 Correct 1557 ms 8108 KB Output is correct
11 Correct 1601 ms 8020 KB Output is correct
12 Correct 56 ms 8020 KB Output is correct
13 Correct 96 ms 8108 KB Output is correct
14 Correct 38 ms 8104 KB Output is correct
15 Correct 304 ms 8104 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1402 ms 8112 KB Output is correct
18 Correct 1525 ms 8104 KB Output is correct
19 Correct 1517 ms 8108 KB Output is correct
20 Correct 1473 ms 8112 KB Output is correct
21 Correct 1614 ms 8120 KB Output is correct
22 Correct 1607 ms 8104 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 3163 ms 8104 KB Output is correct
25 Correct 3183 ms 8108 KB Output is correct
26 Correct 3373 ms 8104 KB Output is correct
27 Correct 3269 ms 8112 KB Output is correct
28 Correct 3177 ms 8104 KB Output is correct
29 Correct 3186 ms 8104 KB Output is correct

Subtask #3-1
0 / 10.0

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

Subtask #3-2
0 / 10.0

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

Subtask #4-1
0 / 10.0

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

Subtask #4-2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 8020 KB Output is correct
2 Correct 99 ms 8112 KB Output is correct
3 Correct 34 ms 8020 KB Output is correct
4 Correct 289 ms 8104 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1418 ms 8120 KB Output is correct
7 Correct 1546 ms 8108 KB Output is correct
8 Correct 1506 ms 8108 KB Output is correct
9 Correct 1572 ms 8112 KB Output is correct
10 Correct 1557 ms 8108 KB Output is correct
11 Correct 1601 ms 8020 KB Output is correct
12 Correct 296 ms 8108 KB Output is correct
13 Incorrect 0 ms 212 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

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

Subtask #5-2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 8020 KB Output is correct
2 Correct 99 ms 8112 KB Output is correct
3 Correct 34 ms 8020 KB Output is correct
4 Correct 289 ms 8104 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1418 ms 8120 KB Output is correct
7 Correct 1546 ms 8108 KB Output is correct
8 Correct 1506 ms 8108 KB Output is correct
9 Correct 1572 ms 8112 KB Output is correct
10 Correct 1557 ms 8108 KB Output is correct
11 Correct 1601 ms 8020 KB Output is correct
12 Correct 56 ms 8020 KB Output is correct
13 Correct 96 ms 8108 KB Output is correct
14 Correct 38 ms 8104 KB Output is correct
15 Correct 304 ms 8104 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1402 ms 8112 KB Output is correct
18 Correct 1525 ms 8104 KB Output is correct
19 Correct 1517 ms 8108 KB Output is correct
20 Correct 1473 ms 8112 KB Output is correct
21 Correct 1614 ms 8120 KB Output is correct
22 Correct 1607 ms 8104 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 3163 ms 8104 KB Output is correct
25 Correct 3183 ms 8108 KB Output is correct
26 Correct 3373 ms 8104 KB Output is correct
27 Correct 3269 ms 8112 KB Output is correct
28 Correct 3177 ms 8104 KB Output is correct
29 Correct 3186 ms 8104 KB Output is correct
30 Correct 296 ms 8108 KB Output is correct
31 Incorrect 0 ms 212 KB Output isn't correct
32 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

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

Subtask #6-2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 8020 KB Output is correct
2 Correct 99 ms 8112 KB Output is correct
3 Correct 34 ms 8020 KB Output is correct
4 Correct 289 ms 8104 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1418 ms 8120 KB Output is correct
7 Correct 1546 ms 8108 KB Output is correct
8 Correct 1506 ms 8108 KB Output is correct
9 Correct 1572 ms 8112 KB Output is correct
10 Correct 1557 ms 8108 KB Output is correct
11 Correct 1601 ms 8020 KB Output is correct
12 Correct 56 ms 8020 KB Output is correct
13 Correct 96 ms 8108 KB Output is correct
14 Correct 38 ms 8104 KB Output is correct
15 Correct 304 ms 8104 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1402 ms 8112 KB Output is correct
18 Correct 1525 ms 8104 KB Output is correct
19 Correct 1517 ms 8108 KB Output is correct
20 Correct 1473 ms 8112 KB Output is correct
21 Correct 1614 ms 8120 KB Output is correct
22 Correct 1607 ms 8104 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 3163 ms 8104 KB Output is correct
25 Correct 3183 ms 8108 KB Output is correct
26 Correct 3373 ms 8104 KB Output is correct
27 Correct 3269 ms 8112 KB Output is correct
28 Correct 3177 ms 8104 KB Output is correct
29 Correct 3186 ms 8104 KB Output is correct
30 Correct 296 ms 8108 KB Output is correct
31 Incorrect 0 ms 212 KB Output isn't correct
32 Halted 0 ms 0 KB -