oj.uz

Submission #1079795

# Submission time Handle Problem Language Result Execution time Memory
1079795 2024-08-29T01:52:21 Z trMatherz Feast (NOI19_feast) C++17
4 / 100
 1000 ms 26816 KB 
#include <iostream> //cin, cout

/*
#include <fstream>
std::ifstream cin ("ex.in");
std::ofstream cout ("ex.out");
*/




// includes
#include <cmath> 
#include <set>
#include <map>
#include <queue>
#include <string>
#include <vector>
#include <array>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <unordered_set>
#include <stack>
#include <ext/pb_ds/assoc_container.hpp>
#include <random>
#include <chrono>
#include <bitset>
#include <complex>


//usings 
using namespace std;
using namespace __gnu_pbds;


// misc
#define ll long long
#define ld long double
#define pb push_back
#define pq priority_queue
#define ub upper_bound
#define lb lower_bound
template<typename T, typename U> bool emin(T &a, const U &b){ return b < a ? a = b, true : false; }
template<typename T, typename U> bool emax(T &a, const U &b){ return b > a ? a = b, true : false; }
typedef uint64_t hash_t;

// vectors
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vpii vector<pair<int, int>>
#define vvpii vector<vector<pair<int, int>>>
#define vppipi vector<pair<int, pair<int, int>>>
#define vl vector<ll>
#define vvl vector<vl>
#define vvvl vector<vvl>
#define vpll vector<pair<ll, ll>>
#define vvpll vector<vpll>
#define vb vector<bool>
#define vvb vector<vb>
#define vs vector<string>
#define sz(x) (int)x.size()
#define rz resize
#define all(x) x.begin(), x.end()
#define vc vector<char>
#define vvc vector<vc>


// pairs
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mp make_pair
#define f first
#define s second

// sets
#define si set<int>
#define sl set<ll>
#define ss set<string>
#define in insert
template <class T> using iset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// maps
#define mii map<int, int>
#define mll map<ll, ll>

// loops
#define FR(x, z, y) for (int x = z; x < y; x++)
#define FRE(x, z, y) FR(x, z, y + 1)
#define F(x, y) FR(x, 0, y)
#define FE(x, y) F(x, y + 1)
#define A(x, y) for(auto &x : y)


vl a; 
int n, k;
pll plop(ll j) {
    vvpll dp(n + 1, vpll(2, {(ll) -1e12, (ll) -1e12}));
    dp[0][0] = {0, 0}; 
    F(i, n){ 
        dp[i + 1][0] = max(dp[i][0], dp[i][1]);
        dp[i + 1][1] = max(mp(dp[i][1].f + a[i], dp[i][1].s), mp(dp[i][0].f + a[i] - j, dp[i][0].s + 1)); 
    }
    return max(mp(dp[n][0].f + j * dp[n][0].s, dp[n][0].s), mp(dp[n][1].f + j * dp[n][1].s, dp[n][1].s)); 
}

int main(){
    cin >> n >> k; 
    a = vl(n); A(u, a) cin >> u;
    ll l = 0, r = (ll) 1e18 + 7; 
    while(l < r) {
        ll m = (l + r) / 2; 
        if(plop(m).s < k) r = m - 1; 
        else l = m ; 
    }
    cout << plop(l).f; 
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 917 ms 26084 KB Output is correct
2 Correct 946 ms 26524 KB Output is correct
3 Correct 962 ms 26816 KB Output is correct
4 Correct 955 ms 26648 KB Output is correct
5 Correct 938 ms 26516 KB Output is correct
6 Correct 972 ms 26072 KB Output is correct
7 Correct 954 ms 26076 KB Output is correct
8 Correct 992 ms 26612 KB Output is correct
9 Correct 984 ms 26120 KB Output is correct
10 Correct 964 ms 26396 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 929 ms 24552 KB Output is correct
2 Correct 997 ms 25176 KB Output is correct
3 Incorrect 952 ms 24488 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1042 ms 344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1042 ms 344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1042 ms 344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 917 ms 26084 KB Output is correct
2 Correct 946 ms 26524 KB Output is correct
3 Correct 962 ms 26816 KB Output is correct
4 Correct 955 ms 26648 KB Output is correct
5 Correct 938 ms 26516 KB Output is correct
6 Correct 972 ms 26072 KB Output is correct
7 Correct 954 ms 26076 KB Output is correct
8 Correct 992 ms 26612 KB Output is correct
9 Correct 984 ms 26120 KB Output is correct
10 Correct 964 ms 26396 KB Output is correct
11 Correct 929 ms 24552 KB Output is correct
12 Correct 997 ms 25176 KB Output is correct
13 Incorrect 952 ms 24488 KB Output isn't correct
14 Halted 0 ms 0 KB -