oj.uz

Submission #534005

# Submission time Handle Problem Language Result Execution time Memory
534005 2022-03-07T19:02:49 Z idas Feast (NOI19_feast) C++11
4 / 100
 132 ms 11348 KB 
#include <bits/stdc++.h>
#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr)
#define FOR(i, begin, end) for(int i = (begin); i < (end); i++)
#define TSTS int ttt; cin >> ttt; while(ttt--) solve()
#define all(x) (x).begin(), (x).end()
#define le(vec) vec[vec.size()-1]
#define sz(x) ((int)((x).size()))
#define pb push_back
#define s second
#define f first

using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef map<int, int> mii;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pdd;

const int INF=1e9, MOD=1e9+7, mod=998244353;
const ll LINF=1e13;

void setIO()
{
    FAST_IO;
}

void setIO(string s)
{
    FAST_IO;
    freopen((s+".in").c_str(), "r", stdin);
    freopen((s+".out").c_str(), "w", stdout);
}

const int N=3e5+10;
int n, k, a[N], cn[N][2];
ll dp[N][2];

bool can(ll x)
{
    FOR(i, 0, n+1) FOR(j, 0, 2) dp[i][j]=cn[i][j]=0;
    dp[0][1]=-INF;
    FOR(i, 1, n+1)
    {
        dp[i][0]=max(dp[i-1][0], dp[i-1][1]);
        if(dp[i-1][0]>dp[i-1][1]){
            cn[i][0]=cn[i-1][0];
        }
        else if(cn[i-1][0]<dp[i-1][1]){
            cn[i][0]=cn[i-1][1];
        }
        else{
            cn[i][0]=min(cn[i-1][0], cn[i-1][1]);
        }

        dp[i][1]=max(dp[i-1][0]+a[i-1]-x, dp[i-1][1]+a[i-1]);
        if(dp[i-1][0]-x>dp[i-1][1]){
            cn[i][1]=cn[i-1][0]+1;
        }
        else if(dp[i-1][0]-x<dp[i-1][1]){
            cn[i][1]=cn[i-1][1];
        }
        else{
            cn[i][1]=min(cn[i-1][0]+1, cn[i-1][1]);
        }
    }

    if(dp[n][0]>dp[n][1]){
        return cn[n][0]<=k;
    }
    else if(dp[n][1]>dp[n][0]){
        return cn[n][1]<=k;
    }
    else{
        return min(cn[n][0], cn[n][1])<=k;
    }
}

ll build(ll x)
{
    FOR(i, 0, n+1) FOR(j, 0, 2) dp[i][j]=cn[i][j]=0;
    dp[0][1]=-INF;
    FOR(i, 1, n+1)
    {
        dp[i][0]=max(dp[i-1][0], dp[i-1][1]);
        if(dp[i-1][0]>dp[i-1][1]){
            cn[i][0]=cn[i-1][0];
        }
        else if(cn[i-1][0]<dp[i-1][1]){
            cn[i][0]=cn[i-1][1];
        }
        else{
            cn[i][0]=min(cn[i-1][0], cn[i-1][1]);
        }

        dp[i][1]=max(dp[i-1][0]+a[i-1]-x, dp[i-1][1]+a[i-1]);
        if(dp[i-1][0]-x>dp[i-1][1]){
            cn[i][1]=cn[i-1][0]+1;
        }
        else if(dp[i-1][0]-x<dp[i-1][1]){
            cn[i][1]=cn[i-1][1];
        }
        else{
            cn[i][1]=min(cn[i-1][0]+1, cn[i-1][1]);
        }
    }

    return max(dp[n][0]+cn[n][0]*x, dp[n][1]+cn[n][1]*x);
}

int main()
{
    setIO();
    cin >> n >> k;
    FOR(i, 0, n) cin >> a[i];

    int l=0, r=INF;
    while(l<r){
        int m=(l+r)/2;
        if(can(m)) r=m;
        else l=m+1;
    }

    cout << build(l);
}

Compilation message

feast.cpp: In function 'void setIO(std::string)':
feast.cpp:32:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     freopen((s+".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
feast.cpp:33:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     freopen((s+".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 8808 KB Output is correct
2 Correct 106 ms 11264 KB Output is correct
3 Correct 85 ms 11268 KB Output is correct
4 Correct 87 ms 11204 KB Output is correct
5 Correct 88 ms 11196 KB Output is correct
6 Correct 87 ms 11012 KB Output is correct
7 Correct 83 ms 11056 KB Output is correct
8 Correct 88 ms 11348 KB Output is correct
9 Correct 93 ms 11092 KB Output is correct
10 Correct 84 ms 11112 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 8312 KB Output is correct
2 Correct 78 ms 9524 KB Output is correct
3 Incorrect 89 ms 9540 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 132 ms 9160 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 8808 KB Output is correct
2 Correct 106 ms 11264 KB Output is correct
3 Correct 85 ms 11268 KB Output is correct
4 Correct 87 ms 11204 KB Output is correct
5 Correct 88 ms 11196 KB Output is correct
6 Correct 87 ms 11012 KB Output is correct
7 Correct 83 ms 11056 KB Output is correct
8 Correct 88 ms 11348 KB Output is correct
9 Correct 93 ms 11092 KB Output is correct
10 Correct 84 ms 11112 KB Output is correct
11 Correct 70 ms 8312 KB Output is correct
12 Correct 78 ms 9524 KB Output is correct
13 Incorrect 89 ms 9540 KB Output isn't correct
14 Halted 0 ms 0 KB -