oj.uz

Submission #534386

# Submission time Handle Problem Language Result Execution time Memory
534386 2022-03-08T06:23:21 Z idas Feast (NOI19_feast) C++11
12 / 100
 114 ms 12636 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=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 90 ms 12152 KB Output is correct
2 Correct 97 ms 12312 KB Output is correct
3 Correct 105 ms 12516 KB Output is correct
4 Correct 97 ms 12468 KB Output is correct
5 Correct 94 ms 12500 KB Output is correct
6 Correct 94 ms 12116 KB Output is correct
7 Correct 97 ms 12212 KB Output is correct
8 Correct 92 ms 12356 KB Output is correct
9 Correct 93 ms 12172 KB Output is correct
10 Correct 88 ms 12352 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 10564 KB Output is correct
2 Correct 80 ms 10808 KB Output is correct
3 Correct 67 ms 10568 KB Output is correct
4 Correct 82 ms 10664 KB Output is correct
5 Correct 85 ms 12108 KB Output is correct
6 Correct 67 ms 10552 KB Output is correct
7 Correct 74 ms 10712 KB Output is correct
8 Correct 88 ms 12500 KB Output is correct
9 Correct 89 ms 12064 KB Output is correct
10 Correct 73 ms 10692 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 114 ms 12636 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 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 1 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 1 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 90 ms 12152 KB Output is correct
2 Correct 97 ms 12312 KB Output is correct
3 Correct 105 ms 12516 KB Output is correct
4 Correct 97 ms 12468 KB Output is correct
5 Correct 94 ms 12500 KB Output is correct
6 Correct 94 ms 12116 KB Output is correct
7 Correct 97 ms 12212 KB Output is correct
8 Correct 92 ms 12356 KB Output is correct
9 Correct 93 ms 12172 KB Output is correct
10 Correct 88 ms 12352 KB Output is correct
11 Correct 56 ms 10564 KB Output is correct
12 Correct 80 ms 10808 KB Output is correct
13 Correct 67 ms 10568 KB Output is correct
14 Correct 82 ms 10664 KB Output is correct
15 Correct 85 ms 12108 KB Output is correct
16 Correct 67 ms 10552 KB Output is correct
17 Correct 74 ms 10712 KB Output is correct
18 Correct 88 ms 12500 KB Output is correct
19 Correct 89 ms 12064 KB Output is correct
20 Correct 73 ms 10692 KB Output is correct
21 Incorrect 114 ms 12636 KB Output isn't correct
22 Halted 0 ms 0 KB -