oj.uz

Submission #534394

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

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

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

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;
ll a[N], p[N];
pair<ll, int> dp[N];

bool can(ll x)
{
    FOR(i, 0, n+1) dp[i]={0,0};
    pair<ll, int> best={0,0};
    FOR(i, 1, n+1)
    {
        dp[i]=max(dp[i-1], {best.f+a[i]-x+p[i],best.s-1});
        best=max(best, {dp[i].f-p[i],dp[i].s});
    }
    return -dp[n].s<=k;
}

ll build(ll x)
{
    FOR(i, 0, n+1) dp[i]={0,0};
    pair<ll, int> best={0,0};
    FOR(i, 1, n+1)
    {
        dp[i]=max(dp[i-1], {best.f-x+p[i],best.s-1});
        best=max(best, {dp[i].f-p[i],dp[i].s});
    }
    return dp[n].f-dp[n].s*x;
}

int  main()
{
    setIO();
    cin >> n >> k;
    FOR(i, 1, n+1) cin >> a[i];
    FOR(i, 1, n+1) p[i]=p[i-1]+a[i];

    int l=-INF, 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 89 ms 9396 KB Output is correct
2 Correct 95 ms 9576 KB Output is correct
3 Correct 114 ms 9680 KB Output is correct
4 Correct 97 ms 9620 KB Output is correct
5 Correct 94 ms 9544 KB Output is correct
6 Correct 96 ms 9412 KB Output is correct
7 Correct 100 ms 9540 KB Output is correct
8 Correct 92 ms 9488 KB Output is correct
9 Correct 87 ms 9424 KB Output is correct
10 Correct 92 ms 9524 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 9364 KB Output is correct
2 Correct 68 ms 9608 KB Output is correct
3 Correct 67 ms 9348 KB Output is correct
4 Correct 77 ms 9548 KB Output is correct
5 Correct 88 ms 9412 KB Output is correct
6 Correct 70 ms 9448 KB Output is correct
7 Correct 78 ms 9688 KB Output is correct
8 Correct 98 ms 9744 KB Output is correct
9 Correct 91 ms 9320 KB Output is correct
10 Correct 77 ms 9636 KB Output is correct

Subtask #3
0 / 18.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 20.0

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

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 9396 KB Output is correct
2 Correct 95 ms 9576 KB Output is correct
3 Correct 114 ms 9680 KB Output is correct
4 Correct 97 ms 9620 KB Output is correct
5 Correct 94 ms 9544 KB Output is correct
6 Correct 96 ms 9412 KB Output is correct
7 Correct 100 ms 9540 KB Output is correct
8 Correct 92 ms 9488 KB Output is correct
9 Correct 87 ms 9424 KB Output is correct
10 Correct 92 ms 9524 KB Output is correct
11 Correct 53 ms 9364 KB Output is correct
12 Correct 68 ms 9608 KB Output is correct
13 Correct 67 ms 9348 KB Output is correct
14 Correct 77 ms 9548 KB Output is correct
15 Correct 88 ms 9412 KB Output is correct
16 Correct 70 ms 9448 KB Output is correct
17 Correct 78 ms 9688 KB Output is correct
18 Correct 98 ms 9744 KB Output is correct
19 Correct 91 ms 9320 KB Output is correct
20 Correct 77 ms 9636 KB Output is correct
21 Incorrect 106 ms 9584 KB Output isn't correct
22 Halted 0 ms 0 KB -