답안 #62776 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
62776	2018-07-30T03:26:25 Z	qkxwsm	Candies (JOI18_candies)	C++17	8 / 100	5000 ms	87604 KB

candies

/*
PROG: source
LANG: C++11
    _____
  .'     '.
 /  0   0  \
|     ^     |
|  \     /  |
 \  '---'  /
  '._____.'
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

struct chash
{
    int operator()(int x) const
	{
		x ^= (x >> 20) ^ (x >> 12);
    	return x ^ (x >> 7) ^ (x >> 4);
	}
	int operator()(long long x) const
	{
		return x ^ (x >> 32);
	}
};

template<typename T> using orderedset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename U> using hashtable = gp_hash_table<T, U, chash>;

template<class T>
void readi(T &x)
{
	T input = 0;
	bool negative = false;
	char c = ' ';
	while (c < '-')
	{
		c = getchar();
	}
	if (c == '-')
	{
		negative = true;
		c = getchar();
	}
	while (c >= '0')
	{
		input = input * 10 + (c - '0');
		c = getchar();
	}
	if (negative)
	{
		input = -input;
	}
	x = input;
}
template<class T>
void printi(T output)
{
	if (output == 0)
	{
		putchar('0');
		return;
	}
	if (output < 0)
	{
		putchar('-');
		output = -output;
	}
	int aout[20];
	int ilen = 0;
	while(output)
	{
		aout[ilen] = ((output % 10));
		output /= 10;
		ilen++;
	}
	for (int i = ilen - 1; i >= 0; i--)
	{
		putchar(aout[i] + '0');
	}
	return;
}
template<class T>
void ckmin(T &a, T b)
{
	a = min(a, b);
}
template<class T>
void ckmax(T &a, T b)
{
	a = max(a, b);
}
template<class T>
T normalize(T x, T mod = 1000000007)
{
	return (((x % mod) + mod) % mod);
}
long long randomizell(long long mod)
{
	return ((1ll << 45) * rand() + (1ll << 30) * rand() + (1ll << 15) * rand() + rand()) % mod;
}
int randomize(int mod)
{
	return ((1ll << 15) * rand() + rand()) % mod;
}

#define y0 ___y0
#define y1 ___y1
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define debug(x) cerr << #x << " = " << x << endl;

const long double PI = 4.0 * atan(1.0);
const long double EPS = 1e-10;

#define MAGIC 347
#define SINF 10007
#define CO 1000007
#define INF 1000000007
#define BIG 1000000931
#define LARGE 1696969696967ll
#define GIANT 2564008813937411ll
#define LLINF 2696969696969696969ll
#define MAXN 200013

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;

int N;
ll arr[MAXN];
vector<ll> seg[3 * MAXN][2][2];

void beat(vector<ll> &a, vector<ll> b)
{
    for (int i = 0; i < b.size(); i++)
    {
        ckmax(a[i], b[i]);
    }
    return;
}
vector<ll> comb(vector<ll> lt, vector<ll> rt)
{
    vector<ll> res(lt.size() + rt.size() - 1), bumps(lt.size() + rt.size() - 2);
    for (int i = 0; i < lt.size(); i++)
    {
        for (int j = 0; j < rt.size(); j++)
        {
            ckmax(res[i + j], lt[i] + rt[j]);
        }
    }
    return res;
    for (int i = 1; i < lt.size(); i++)
    {
        bumps[i - 1] = lt[i] - lt[i - 1];
    }
    for (int i = 1; i < rt.size(); i++)
    {
        bumps[lt.size() + i - 2] = rt[i] - rt[i - 1];
    }
    sort(bumps.begin(), bumps.end());
    reverse(bumps.begin(), bumps.end());
    res[0] = lt[0] + rt[0];
    for (int i = 1; i < res.size(); i++)
    {
        res[i] = res[i - 1] + bumps[i - 1];
    }
    return res;
}
void solve(int w, int L, int R)
{
    seg[w][0][0].resize((R - L + 2)/ 2);
    seg[w][0][1].resize((R - L + 3)/ 2);
    seg[w][1][0].resize((R - L + 3)/ 2);
    seg[w][1][1].resize((R - L + 4)/ 2);
    if (L == R)
    {
        seg[w][1][1][1] = arr[L];
        return;
    }
    int mid = (L + R) >> 1;
    solve(2 * w, L, mid);
    solve(2 * w + 1, mid + 1, R);
    for (int i = 0; i < 2; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            beat(seg[w][i][j], comb(seg[2 * w][i][0], seg[2 * w + 1][0][j]));
            beat(seg[w][i][j], comb(seg[2 * w][i][0], seg[2 * w + 1][1][j]));
            beat(seg[w][i][j], comb(seg[2 * w][i][1], seg[2 * w + 1][0][j]));
        }
    }
    // cerr << "for " << L << ' ' << R << endl;
    // cerr << seg[w][1][1][1] << ' ' << seg[w][0][0][0] << endl;
    return;
}

int32_t main()
{
	ios_base::sync_with_stdio(0);
	srand(time(0));
	//	cout << fixed << setprecision(10);
	//	cerr << fixed << setprecision(10);
	if (fopen("input.in", "r"))
	{
		freopen ("input.in", "r", stdin);
		freopen ("output.out", "w", stdout);
	}
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> arr[i];
    }
    solve(1, 0, N - 1);
    for (int i = 1; i <= (N + 1) / 2; i++)
    {
        cout << seg[1][1][1][i] << '\n';
    }
	//	cerr << "time elapsed = " << (clock() / (CLOCKS_PER_SEC / 1000)) << " ms" << endl;
	return 0;
}

Compilation message

candies.cpp: In function 'void beat(std::vector<long long int>&, std::vector<long long int>)':
candies.cpp:149:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < b.size(); i++)
                     ~~^~~~~~~~~~
candies.cpp: In function 'std::vector<long long int> comb(std::vector<long long int>, std::vector<long long int>)':
candies.cpp:158:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < lt.size(); i++)
                     ~~^~~~~~~~~~~
candies.cpp:160:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < rt.size(); j++)
                         ~~^~~~~~~~~~~
candies.cpp:166:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < lt.size(); i++)
                     ~~^~~~~~~~~~~
candies.cpp:170:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < rt.size(); i++)
                     ~~^~~~~~~~~~~
candies.cpp:177:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < res.size(); i++)
                     ~~^~~~~~~~~~~~
candies.cpp: In function 'int32_t main()':
candies.cpp:219:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen ("input.in", "r", stdin);
   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
candies.cpp:220:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen ("output.out", "w", stdout);
   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	69 ms	57464 KB	Output is correct
2	Correct	71 ms	57716 KB	Output is correct
3	Correct	69 ms	57788 KB	Output is correct
4	Correct	77 ms	57820 KB	Output is correct
5	Correct	73 ms	57844 KB	Output is correct
6	Correct	69 ms	57844 KB	Output is correct
7	Correct	69 ms	57844 KB	Output is correct
8	Correct	69 ms	57844 KB	Output is correct
9	Correct	73 ms	57844 KB	Output is correct
10	Correct	69 ms	57844 KB	Output is correct
11	Correct	74 ms	57900 KB	Output is correct
12	Correct	74 ms	57900 KB	Output is correct
13	Correct	68 ms	57900 KB	Output is correct
14	Correct	69 ms	57900 KB	Output is correct
15	Correct	71 ms	57900 KB	Output is correct
16	Correct	68 ms	57900 KB	Output is correct
17	Correct	72 ms	57900 KB	Output is correct
18	Correct	68 ms	57900 KB	Output is correct
19	Correct	69 ms	57900 KB	Output is correct
20	Correct	68 ms	58028 KB	Output is correct

Subtask #2
0 / 92.0

#	결과	실행 시간	메모리	Grader output
1	Correct	69 ms	57464 KB	Output is correct
2	Correct	71 ms	57716 KB	Output is correct
3	Correct	69 ms	57788 KB	Output is correct
4	Correct	77 ms	57820 KB	Output is correct
5	Correct	73 ms	57844 KB	Output is correct
6	Correct	69 ms	57844 KB	Output is correct
7	Correct	69 ms	57844 KB	Output is correct
8	Correct	69 ms	57844 KB	Output is correct
9	Correct	73 ms	57844 KB	Output is correct
10	Correct	69 ms	57844 KB	Output is correct
11	Correct	74 ms	57900 KB	Output is correct
12	Correct	74 ms	57900 KB	Output is correct
13	Correct	68 ms	57900 KB	Output is correct
14	Correct	69 ms	57900 KB	Output is correct
15	Correct	71 ms	57900 KB	Output is correct
16	Correct	68 ms	57900 KB	Output is correct
17	Correct	72 ms	57900 KB	Output is correct
18	Correct	68 ms	57900 KB	Output is correct
19	Correct	69 ms	57900 KB	Output is correct
20	Correct	68 ms	58028 KB	Output is correct
21	Execution timed out	5063 ms	87604 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-

답안 #62776

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 0 / 92.0

Subtask #1
8.0 / 8.0

Subtask #2
0 / 92.0