oj.uz

답안 #580500

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
580500 2022-06-21T10:54:21 Z urd05 Uplifting Excursion (BOI22_vault) C++17
0 / 100
 1399 ms 8140 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);
    for(int i=1;i<=m*2+1;i++) {
        scanf("%lld",&arr[i]);
    }
    long long total=l;
    if (l<0) {
        printf("impossible");
        return 0;
    }
    long long ret=0;
    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);
        ret+=use;
        if (arr[i]>100) {
            arr[i]=100;
        }
    }
    for(int i=0;i<=zero*2;i++) {
        dp0[i]=-1e7;
        dp[i]=-1e7;
    }
    if (l>zero||l<-zero) {
        printf("impossible");
        return 0;
    }
    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("%lld",ret+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:15:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |         scanf("%lld",&arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 8104 KB Output is correct
2 Correct 97 ms 8108 KB Output is correct
3 Correct 37 ms 8020 KB Output is correct
4 Correct 266 ms 8104 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1399 ms 8104 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Incorrect 1 ms 212 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 8104 KB Output is correct
2 Correct 97 ms 8108 KB Output is correct
3 Correct 37 ms 8020 KB Output is correct
4 Correct 266 ms 8104 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1399 ms 8104 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Incorrect 1 ms 212 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 280 ms 8108 KB Output is correct
2 Correct 856 ms 8124 KB Output is correct
3 Correct 896 ms 8140 KB Output is correct
4 Incorrect 851 ms 8112 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 280 ms 8108 KB Output is correct
2 Correct 856 ms 8124 KB Output is correct
3 Correct 896 ms 8140 KB Output is correct
4 Incorrect 851 ms 8112 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 280 ms 8108 KB Output is correct
2 Correct 856 ms 8124 KB Output is correct
3 Correct 896 ms 8140 KB Output is correct
4 Incorrect 851 ms 8112 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 8104 KB Output is correct
2 Correct 97 ms 8108 KB Output is correct
3 Correct 37 ms 8020 KB Output is correct
4 Correct 266 ms 8104 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1399 ms 8104 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Incorrect 1 ms 212 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 280 ms 8108 KB Output is correct
2 Correct 856 ms 8124 KB Output is correct
3 Correct 896 ms 8140 KB Output is correct
4 Incorrect 851 ms 8112 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 8104 KB Output is correct
2 Correct 97 ms 8108 KB Output is correct
3 Correct 37 ms 8020 KB Output is correct
4 Correct 266 ms 8104 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1399 ms 8104 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Incorrect 1 ms 212 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 280 ms 8108 KB Output is correct
2 Correct 856 ms 8124 KB Output is correct
3 Correct 896 ms 8140 KB Output is correct
4 Incorrect 851 ms 8112 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 8104 KB Output is correct
2 Correct 97 ms 8108 KB Output is correct
3 Correct 37 ms 8020 KB Output is correct
4 Correct 266 ms 8104 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1399 ms 8104 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Incorrect 1 ms 212 KB Output isn't correct
9 Halted 0 ms 0 KB -