oj.uz

Submission #551311

# Submission time Handle Problem Language Result Execution time Memory
551311 2022-04-20T09:01:41 Z AA_Surely Candies (JOI18_candies) C++17
8 / 100
 5000 ms 106024 KB 
#include <bits/stdc++.h>

#define FOR(i,x,n) 	for(int i=x; i<n; i++)
#define F0R(i,n) 	FOR(i,0,n)
#define ROF(i,x,n) 	for(int i=n-1; i>=x; i--)
#define R0F(i,n) 	ROF(i,0,n)

#define WTF 		cout << "WTF" << endl

#define IOS 		ios::sync_with_stdio(false); cin.tie(0)
#define F 			first
#define S	 		second
#define pb 			push_back

#define ALL(x) 		x.begin(), x.end()
#define RALL(x) 	x.rbegin(), x.rend()

using namespace std;
typedef long long 		LL;

typedef pair<int, int> 	PII;
typedef pair<LL, LL> 	PLL;

typedef vector<int> 	VI;
typedef vector<LL> 		VLL;
typedef vector<PII> 	VPII;
typedef vector<PLL> 	VPLL;

const int N = 2e5 + 7;
const int ALPHA = 27;
const LL INF = 5e17 + 7;
const int MOD = 1e9 + 7;
const int LOG = 22;

#define lc now << 1
#define rc now << 1 | 1

struct Node {
    VLL v[2][2];
} tree[N << 2];

LL n;
LL ns[N];

inline void merge(Node &a, Node b, Node c) {
    F0R(i, 2) F0R(j, 2) {
        a.v[i][j].resize(b.v[1][1].size() + c.v[1][1].size());
        F0R(k, a.v[i][j].size()) a.v[i][j][k] = -INF;
    }
    
    F0R(l, 2) F0R(r, 2) F0R(i, b.v[1][1].size()) F0R(j, c.v[1][1].size()) 
        a.v[l][r][i + j] = max({a.v[l][r][i + j], 
                                b.v[l][0][i] + max(c.v[0][r][j], c.v[1][r][j]), 
                                max(b.v[l][0][i], b.v[l][1][i]) + c.v[0][r][j]});
    return;
}

void build(int now = 1, int ls = 0, int rs = n - 1) {
    if (ls == rs) {
        F0R(i, 2) F0R(j, 2) {
            tree[now].v[i][j].pb(0);
            tree[now].v[i][j].pb(-INF);
        }

        tree[now].v[1][1].pop_back();
        tree[now].v[1][1].pb(ns[ls]);
        return;
    }

    int mid = (ls + rs) >> 1;
    build(lc, ls, mid); build(rc, mid + 1, rs);
    merge(tree[now], tree[lc], tree[rc]);
    return;
}

int main() {
    IOS;
    
    cin >> n;
    F0R(i, n) cin >> ns[i];
    build();

    FOR(i, 1, (n >> 1) + (n & 1) + 1) {
        LL mx = 0;
        F0R(x, 2) F0R(y, 2) mx = max(mx, tree[1].v[x][y][i]);
        if (i != 1) cout << '\n';
        cout << mx;
    }
    
    return 0;
}

Compilation message

candies.cpp: In function 'void merge(Node&, Node, Node)':
candies.cpp:3:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define FOR(i,x,n)  for(int i=x; i<n; i++)
      |                                   ^
candies.cpp:4:19: note: in expansion of macro 'FOR'
    4 | #define F0R(i,n)  FOR(i,0,n)
      |                   ^~~
candies.cpp:48:9: note: in expansion of macro 'F0R'
   48 |         F0R(k, a.v[i][j].size()) a.v[i][j][k] = -INF;
      |         ^~~
candies.cpp:3:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define FOR(i,x,n)  for(int i=x; i<n; i++)
      |                                   ^
candies.cpp:4:19: note: in expansion of macro 'FOR'
    4 | #define F0R(i,n)  FOR(i,0,n)
      |                   ^~~
candies.cpp:51:25: note: in expansion of macro 'F0R'
   51 |     F0R(l, 2) F0R(r, 2) F0R(i, b.v[1][1].size()) F0R(j, c.v[1][1].size())
      |                         ^~~
candies.cpp:3:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define FOR(i,x,n)  for(int i=x; i<n; i++)
      |                                   ^
candies.cpp:4:19: note: in expansion of macro 'FOR'
    4 | #define F0R(i,n)  FOR(i,0,n)
      |                   ^~~
candies.cpp:51:50: note: in expansion of macro 'F0R'
   51 |     F0R(l, 2) F0R(r, 2) F0R(i, b.v[1][1].size()) F0R(j, c.v[1][1].size())
      |                                                  ^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 77352 KB Output is correct
2 Correct 106 ms 77296 KB Output is correct
3 Correct 104 ms 77388 KB Output is correct
4 Correct 105 ms 77388 KB Output is correct
5 Correct 107 ms 77396 KB Output is correct
6 Correct 106 ms 77332 KB Output is correct
7 Correct 111 ms 77408 KB Output is correct
8 Correct 105 ms 77400 KB Output is correct
9 Correct 104 ms 77364 KB Output is correct
10 Correct 107 ms 77332 KB Output is correct
11 Correct 107 ms 77392 KB Output is correct
12 Correct 121 ms 77292 KB Output is correct
13 Correct 111 ms 77404 KB Output is correct
14 Correct 108 ms 77276 KB Output is correct
15 Correct 106 ms 77316 KB Output is correct
16 Correct 113 ms 77396 KB Output is correct
17 Correct 108 ms 77388 KB Output is correct
18 Correct 105 ms 77332 KB Output is correct
19 Correct 109 ms 77292 KB Output is correct
20 Correct 105 ms 77316 KB Output is correct

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 77352 KB Output is correct
2 Correct 106 ms 77296 KB Output is correct
3 Correct 104 ms 77388 KB Output is correct
4 Correct 105 ms 77388 KB Output is correct
5 Correct 107 ms 77396 KB Output is correct
6 Correct 106 ms 77332 KB Output is correct
7 Correct 111 ms 77408 KB Output is correct
8 Correct 105 ms 77400 KB Output is correct
9 Correct 104 ms 77364 KB Output is correct
10 Correct 107 ms 77332 KB Output is correct
11 Correct 107 ms 77392 KB Output is correct
12 Correct 121 ms 77292 KB Output is correct
13 Correct 111 ms 77404 KB Output is correct
14 Correct 108 ms 77276 KB Output is correct
15 Correct 106 ms 77316 KB Output is correct
16 Correct 113 ms 77396 KB Output is correct
17 Correct 108 ms 77388 KB Output is correct
18 Correct 105 ms 77332 KB Output is correct
19 Correct 109 ms 77292 KB Output is correct
20 Correct 105 ms 77316 KB Output is correct
21 Execution timed out 5014 ms 106024 KB Time limit exceeded
22 Halted 0 ms 0 KB -