| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 671120 | 2022-12-12T04:53:47 Z | vuavisao | Feast (NOI19_feast) | C++14 | 64 ms | 30712 KB |
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define ll long long
using namespace std;
template<typename Lhs, typename Rhs> inline bool Max_self(Lhs &a, Rhs b) { if(b > a) { a = b; return true; } return false; }
template<typename Lhs, typename Rhs> inline bool Min_self(Lhs &a, Rhs b) { if(b < a) { a = b; return true; } return false; }
const ll N = 3e5 + 10;
const ll INF = 1e18;
ll n, k, a[N];
namespace sub6 {
bool check() {
return (n <= 2000);
}
ll dp[2010][2010];
ll res;
void solve() {
for(ll gr = 1; gr <= k; ++ gr) {
for(ll i = 1; i <= n; ++ i) {
Max_self(dp[i][gr], dp[i - 1][gr] + a[i]);
Max_self(dp[i][gr], dp[i - 1][gr - 1] + a[i]);
}
for(ll i = 1; i <= n; ++ i) Max_self(dp[i][gr], dp[i - 1][gr]);
Max_self(res, dp[n][gr]);
}
cout << res;
}
}
namespace last_sub {
ll dp[N], cnt[N];
bool check(ll lamba) {
ll best[2] = {0, 1};
cnt[0] = 1;
for(ll i = 1; i <= n; ++ i) {
dp[i] = - INF;
Max_self(dp[i], dp[i - 1] + a[i] - lamba);
cnt[i] = cnt[i - 1];
if(Max_self(dp[i], dp[best[0]] + a[i] - lamba)) cnt[i] = cnt[best[1]] + 1;
cout << i << ": " << dp[i] << ' ' << cnt[i] << '\n';
if(Max_self(best[0], dp[i])) {
best[1] = cnt[i];
}
}
return (cnt[n] <= k);
}
void solve() {
cout << check(0) << '\n';
// ll l = 0, r = INF;
// ll lamba = - 1;
// while(l <= r) {
// ll mid = (l + r) >> 1ll;
// if(check(mid)) {
// lamba = mid;
// r = mid - 1;
// }
// else l = mid + 1;
// }
// assert(lamba != - 1);
// check(lamba);
// cout << dp[n] << ' ' << cnt[n] << '\n';
// cout << dp[n] + lamba * cnt[n];
}
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if (fopen("Feast.inp", "r")) {
freopen("Feast.inp", "r", stdin);
freopen("Feast.out", "w", stdout);
}
cin >> n >> k;
for(ll i = 1; i <= n; ++ i) cin >> a[i];
if(sub6::check()) {
sub6::solve();
return 0;
}
assert(false);
// last_sub::solve();
return 0;
}
/// Code by vuavisao
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 30 ms | 7832 KB | Execution killed with signal 6 |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 21 ms | 6164 KB | Execution killed with signal 6 |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 34 ms | 8216 KB | Execution killed with signal 6 |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 596 KB | Output is correct |
| 2 | Correct | 1 ms | 584 KB | Output is correct |
| 3 | Correct | 1 ms | 596 KB | Output is correct |
| 4 | Correct | 1 ms | 588 KB | Output is correct |
| 5 | Correct | 1 ms | 596 KB | Output is correct |
| 6 | Correct | 1 ms | 596 KB | Output is correct |
| 7 | Correct | 1 ms | 596 KB | Output is correct |
| 8 | Correct | 1 ms | 596 KB | Output is correct |
| 9 | Correct | 1 ms | 596 KB | Output is correct |
| 10 | Correct | 1 ms | 596 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 596 KB | Output is correct |
| 2 | Correct | 1 ms | 584 KB | Output is correct |
| 3 | Correct | 1 ms | 596 KB | Output is correct |
| 4 | Correct | 1 ms | 588 KB | Output is correct |
| 5 | Correct | 1 ms | 596 KB | Output is correct |
| 6 | Correct | 1 ms | 596 KB | Output is correct |
| 7 | Correct | 1 ms | 596 KB | Output is correct |
| 8 | Correct | 1 ms | 596 KB | Output is correct |
| 9 | Correct | 1 ms | 596 KB | Output is correct |
| 10 | Correct | 1 ms | 596 KB | Output is correct |
| 11 | Correct | 1 ms | 1620 KB | Output is correct |
| 12 | Correct | 1 ms | 1492 KB | Output is correct |
| 13 | Correct | 2 ms | 1368 KB | Output is correct |
| 14 | Correct | 1 ms | 1492 KB | Output is correct |
| 15 | Correct | 1 ms | 1480 KB | Output is correct |
| 16 | Correct | 1 ms | 1364 KB | Output is correct |
| 17 | Correct | 1 ms | 1492 KB | Output is correct |
| 18 | Correct | 1 ms | 1364 KB | Output is correct |
| 19 | Correct | 1 ms | 1356 KB | Output is correct |
| 20 | Correct | 1 ms | 1492 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 596 KB | Output is correct |
| 2 | Correct | 1 ms | 584 KB | Output is correct |
| 3 | Correct | 1 ms | 596 KB | Output is correct |
| 4 | Correct | 1 ms | 588 KB | Output is correct |
| 5 | Correct | 1 ms | 596 KB | Output is correct |
| 6 | Correct | 1 ms | 596 KB | Output is correct |
| 7 | Correct | 1 ms | 596 KB | Output is correct |
| 8 | Correct | 1 ms | 596 KB | Output is correct |
| 9 | Correct | 1 ms | 596 KB | Output is correct |
| 10 | Correct | 1 ms | 596 KB | Output is correct |
| 11 | Correct | 1 ms | 1620 KB | Output is correct |
| 12 | Correct | 1 ms | 1492 KB | Output is correct |
| 13 | Correct | 2 ms | 1368 KB | Output is correct |
| 14 | Correct | 1 ms | 1492 KB | Output is correct |
| 15 | Correct | 1 ms | 1480 KB | Output is correct |
| 16 | Correct | 1 ms | 1364 KB | Output is correct |
| 17 | Correct | 1 ms | 1492 KB | Output is correct |
| 18 | Correct | 1 ms | 1364 KB | Output is correct |
| 19 | Correct | 1 ms | 1356 KB | Output is correct |
| 20 | Correct | 1 ms | 1492 KB | Output is correct |
| 21 | Correct | 12 ms | 11096 KB | Output is correct |
| 22 | Correct | 64 ms | 30712 KB | Output is correct |
| 23 | Correct | 21 ms | 13924 KB | Output is correct |
| 24 | Correct | 14 ms | 11348 KB | Output is correct |
| 25 | Correct | 18 ms | 12944 KB | Output is correct |
| 26 | Correct | 12 ms | 11072 KB | Output is correct |
| 27 | Correct | 19 ms | 12596 KB | Output is correct |
| 28 | Correct | 7 ms | 8788 KB | Output is correct |
| 29 | Correct | 6 ms | 8660 KB | Output is correct |
| 30 | Correct | 5 ms | 8148 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 30 ms | 7832 KB | Execution killed with signal 6 |
| 2 | Halted | 0 ms | 0 KB | - |