oj.uz

Submission #551313

# Submission time Handle Problem Language Result Execution time Memory
551313 2022-04-20T09:04:26 Z AA_Surely Candies (JOI18_candies) C++14
8 / 100
 5000 ms 103076 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]});

    while(a.v[1][1].back() == INF) {
        a.v[1][1].pop_back();
        a.v[1][0].pop_back();
        a.v[0][1].pop_back();
        a.v[0][0].pop_back();
    }

    F0R(i, 2) F0R(j, 2) {
        b.v[i][j].clear();
        c.v[i][j].clear();
    }
    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 121 ms 77132 KB Output is correct
2 Correct 111 ms 77268 KB Output is correct
3 Correct 116 ms 77232 KB Output is correct
4 Correct 113 ms 77184 KB Output is correct
5 Correct 119 ms 77144 KB Output is correct
6 Correct 114 ms 77212 KB Output is correct
7 Correct 120 ms 77232 KB Output is correct
8 Correct 113 ms 77224 KB Output is correct
9 Correct 125 ms 77200 KB Output is correct
10 Correct 119 ms 77352 KB Output is correct
11 Correct 117 ms 77292 KB Output is correct
12 Correct 124 ms 77120 KB Output is correct
13 Correct 114 ms 77312 KB Output is correct
14 Correct 115 ms 77236 KB Output is correct
15 Correct 114 ms 77180 KB Output is correct
16 Correct 116 ms 77244 KB Output is correct
17 Correct 112 ms 77132 KB Output is correct
18 Correct 124 ms 77312 KB Output is correct
19 Correct 108 ms 77264 KB Output is correct
20 Correct 109 ms 77224 KB Output is correct

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 77132 KB Output is correct
2 Correct 111 ms 77268 KB Output is correct
3 Correct 116 ms 77232 KB Output is correct
4 Correct 113 ms 77184 KB Output is correct
5 Correct 119 ms 77144 KB Output is correct
6 Correct 114 ms 77212 KB Output is correct
7 Correct 120 ms 77232 KB Output is correct
8 Correct 113 ms 77224 KB Output is correct
9 Correct 125 ms 77200 KB Output is correct
10 Correct 119 ms 77352 KB Output is correct
11 Correct 117 ms 77292 KB Output is correct
12 Correct 124 ms 77120 KB Output is correct
13 Correct 114 ms 77312 KB Output is correct
14 Correct 115 ms 77236 KB Output is correct
15 Correct 114 ms 77180 KB Output is correct
16 Correct 116 ms 77244 KB Output is correct
17 Correct 112 ms 77132 KB Output is correct
18 Correct 124 ms 77312 KB Output is correct
19 Correct 108 ms 77264 KB Output is correct
20 Correct 109 ms 77224 KB Output is correct
21 Execution timed out 5069 ms 103076 KB Time limit exceeded
22 Halted 0 ms 0 KB -