oj.uz

Submission #421738

# Submission time Handle Problem Language Result Execution time Memory
421738 2021-06-09T11:31:31 Z vulpes2 Candies (JOI18_candies) C++17
8 / 100
 255 ms 524292 KB 
//#include <atcoder/maxflow.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
 

#include <iostream>
#include <map>
#include <list>
#include <set>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <iterator>
#include <random>
#include <chrono>
#include <complex>
#include <bitset>
#include <fstream>
 
 
#define forr(i,start,count) for (int i = (start); i < (start)+(count); ++i)
#define set_map_includes(set, elt) (set.find((elt)) != set.end())
#define readint(i) int i; cin >> i
#define readll(i) ll i; cin >> i
#define readdouble(i) double i; cin >> i
#define readstring(s) string s; cin >> s

typedef long long ll;

 
//using namespace __gnu_pbds;
//using namespace atcoder;
using namespace std;

const ll modd = (1000LL * 1000LL * 1000LL + 7LL);
//const ll modd = 998244353;

int main(int argc, char *argv[])   {

    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    uniform_int_distribution<int> rand_gen(0, modd);   // rand_gen(rng) gets the rand no

    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cout.precision(12);

//    readint(test_cases);
    int test_cases = 1;
    forr(t, 1, test_cases) {
        readint(n);
        vector<ll> a(n+1);
        forr(i,1,n) {
            readint(aa);
            a[i] = aa;
        } 

        vector<vector<ll>> maxp(n+1, vector<ll>(n+1, -modd*modd)), maxn(n+1, vector<ll>(n+1, -modd*modd));
        maxn[0][0] = 0;
        forr(i,1,n) {
            maxn[i][0] = 0;
            forr(j,1,n-1) {
                maxp[i][j] = a[i]+maxn[i-1][j-1];
                maxn[i][j] = max(maxp[i-1][j], maxn[i-1][j]);
            }
        }
        forr(i,1,n) {
            cout << max(maxp[n][i], maxn[n][i]) << endl;
            if (2*i+1>n) break;
        }
    }

    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 63052 KB Output is correct
2 Correct 37 ms 63156 KB Output is correct
3 Correct 38 ms 63044 KB Output is correct
4 Correct 37 ms 63168 KB Output is correct
5 Correct 38 ms 63044 KB Output is correct
6 Correct 39 ms 63152 KB Output is correct
7 Correct 45 ms 63128 KB Output is correct
8 Correct 37 ms 63236 KB Output is correct
9 Correct 39 ms 63124 KB Output is correct
10 Correct 38 ms 63048 KB Output is correct
11 Correct 43 ms 63092 KB Output is correct
12 Correct 38 ms 63112 KB Output is correct
13 Correct 53 ms 63068 KB Output is correct
14 Correct 46 ms 63052 KB Output is correct
15 Correct 37 ms 63136 KB Output is correct
16 Correct 39 ms 63028 KB Output is correct
17 Correct 37 ms 63100 KB Output is correct
18 Correct 37 ms 63044 KB Output is correct
19 Correct 37 ms 63052 KB Output is correct
20 Correct 37 ms 63052 KB Output is correct

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 63052 KB Output is correct
2 Correct 37 ms 63156 KB Output is correct
3 Correct 38 ms 63044 KB Output is correct
4 Correct 37 ms 63168 KB Output is correct
5 Correct 38 ms 63044 KB Output is correct
6 Correct 39 ms 63152 KB Output is correct
7 Correct 45 ms 63128 KB Output is correct
8 Correct 37 ms 63236 KB Output is correct
9 Correct 39 ms 63124 KB Output is correct
10 Correct 38 ms 63048 KB Output is correct
11 Correct 43 ms 63092 KB Output is correct
12 Correct 38 ms 63112 KB Output is correct
13 Correct 53 ms 63068 KB Output is correct
14 Correct 46 ms 63052 KB Output is correct
15 Correct 37 ms 63136 KB Output is correct
16 Correct 39 ms 63028 KB Output is correct
17 Correct 37 ms 63100 KB Output is correct
18 Correct 37 ms 63044 KB Output is correct
19 Correct 37 ms 63052 KB Output is correct
20 Correct 37 ms 63052 KB Output is correct
21 Runtime error 255 ms 524292 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -