oj.uz

Submission #551308

# Submission time Handle Problem Language Result Execution time Memory
551308 2022-04-20T08:59:07 Z AA_Surely Candies (JOI18_candies) C++17
0 / 100
 103 ms 77340 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 int INF = 1e9 + 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]);
        cout << mx << '\n';
    }
    
    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
0 / 8.0

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

Subtask #2
0 / 92.0

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