Submission #4721481
Source Code Expand
// This is free and unencumbered software released into the public domain.
// Anyone is free to copy, modify, publish, use, compile, sell, or
// distribute this software, either in source code form or as a compiled
// binary, for any purpose, commercial or non-commercial, and by any
// means.
// In jurisdictions that recognize copyright laws, the author or authors
// of this software dedicate any and all copyright interest in the
// software to the public domain. We make this dedication for the benefit
// of the public at large and to the detriment of our heirs and
// successors. We intend this dedication to be an overt act of
// relinquishment in perpetuity of all present and future rights to this
// software under copyright law.
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
// IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
// OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
// ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
// OTHER DEALINGS IN THE SOFTWARE.
// For more information, please refer to <http://unlicense.org>
/****************/
/* template.hpp */
/****************/
#include <cassert>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
using std::abs;
using std::cerr;
using std::cout;
using std::endl;
using std::max;
using std::min;
using std::numeric_limits;
using std::swap;
struct BoolName : std::numpunct<char> {
std::string t, f;
BoolName (std::string t, std::string f) : t(t), f(f) {}
std::string do_truename() const {return t;}
std::string do_falsename() const {return f;}
};
void set_bool_name(std::string t, std::string f) {
cout.imbue(std::locale(cout.getloc(), new BoolName(t, f)));
}
struct Initializer {
Initializer() {
cout << std::fixed << std::setprecision(15) << std::boolalpha;
set_bool_name("Yes", "No");
}
} initializer;
struct Input {
bool eof;
Input() : eof(false) {}
operator char() {
char v;
this->eof = (std::scanf("%c", &v) != 1);
return v;
}
operator int() {
int v;
this->eof = (std::scanf("%d", &v) != 1);
return v;
}
operator long() {
long v;
this->eof = (std::scanf("%ld", &v) != 1);
return v;
}
operator long long() {
long long v;
this->eof = (std::scanf("%lld", &v) != 1);
return v;
}
operator unsigned int() {
unsigned int v;
this->eof = (std::scanf("%u", &v) != 1);
return v;
}
operator unsigned long() {
unsigned long v;
this->eof = (std::scanf("%lu", &v) != 1);
return v;
}
operator unsigned long long() {
unsigned long long v;
this->eof = (std::scanf("%llu", &v) != 1);
return v;
}
operator double() {
double v;
this->eof = (std::scanf("%lf", &v) != 1);
return v;
}
operator long double() {
long double v;
this->eof = (std::scanf("%Lf", &v) != 1);
return v;
}
void ignore() const {
getchar();
}
} in;
template<typename T> bool chmin(T& a, T b) {return a > b ? a = b, true : false;}
template<typename T> bool chmax(T& a, T b) {return a < b ? a = b, true : false;}
template<typename T, typename S> std::function<S(T)> cast() {
return [](const T& t) { return static_cast<S>(t); };
}
/******************/
/* arithmetic.hpp */
/******************/
template<typename T> class Addition {
public:
template<typename V> T operator+(const V& v) const {
return T(static_cast<const T&>(*this)) += v;
}
T operator++() {
return static_cast<T&>(*this) += 1;
}
};
template<typename T> class Subtraction {
public:
template<typename V> T operator-(const V& v) const {
return T(static_cast<const T&>(*this)) -= v;
}
};
template<typename T> class Multiplication {
public:
template<typename V> T operator*(const V& v) const {
return T(static_cast<const T&>(*this)) *= v;
}
};
template<typename T> class Division {
public:
template<typename V> T operator/(const V& v) const {
return T(static_cast<const T&>(*this)) /= v;
}
};
template<typename T> class Modulus {
public:
template<typename V> T operator%(const V& v) const {
return T(static_cast<const T&>(*this)) %= v;
}
};
template<typename T> class IndivisibleArithmetic : public Addition<T>, public Subtraction<T>, public Multiplication<T> {};
template<typename T> class Arithmetic : public IndivisibleArithmetic<T>, public Division<T> {};
/*****************/
/* container.hpp */
/*****************/
#include <algorithm>
#include <vector>
template<typename T> class Container : public T {
private:
using S = typename T::value_type;
public:
Container() : T() {}
Container(int n) : T(n) {}
Container(int n, S s) : T(n, s) {}
template<typename Itr> Container(Itr first, Itr last) : T(first, last) {}
Container(const std::initializer_list<S>& v) : T(v) {}
Container(int n, Input& in) {
std::vector<S> v(n);
for (auto& i : v) {
i = in;
}
*this = Container<T>(v.begin(), v.end());
}
S max() const {
return *max_element(this->begin(), this->end());
}
template<typename Function> auto max(Function func) const {
std::vector<decltype(func(S()))> res;
std::transform(this->begin(), this->end(), std::back_inserter(res), func);
return *max_element(res.begin(), res.end());
}
S min() const {
return *min_element(this->begin(), this->end());
}
int argmax() const {
return max_element(this->begin(), this->end()) - this->begin();
}
int argmin() const {
return min_element(this->begin(), this->end()) - this->begin();
}
bool contains(const S& a) const {
return find(this->begin(), this->end(), a) != this->end();
}
int size() const { return T::size(); }
};
/***************/
/* ordered.hpp */
/***************/
template<typename T> class Ordered {
public:
template<typename V> bool operator==(const V& v) const {
return !(static_cast<T>(v) < static_cast<const T&>(*this) || static_cast<const T&>(*this) < static_cast<T>(v));
}
template<typename V> bool operator!=(const V& v) const {
return static_cast<T>(v) < static_cast<const T&>(*this) || static_cast<const T&>(*this) < static_cast<T>(v);
}
template<typename V> bool operator>(const V& v) const {
return static_cast<T>(v) < static_cast<const T&>(*this);
}
template<typename V> bool operator<=(const V& v) const {
return !(static_cast<T>(v) < static_cast<const T&>(*this));
}
template<typename V> bool operator>=(const V& v) const {
return !(static_cast<const T&>(*this) < static_cast<T>(v));
}
};
/**************/
/* vector.hpp */
/**************/
#include <numeric>
template<typename T> class Vector : public Container<std::vector<T>>, public Arithmetic<Vector<T>>, public Modulus<Vector<T>>, public Ordered<Vector<T>> {
public:
Vector() = default;
Vector(const Vector<T>& v) = default;
Vector(int n) : Container<std::vector<T>>(n) {}
Vector(int n, T t) : Container<std::vector<T>>(n, t) {}
template<typename Itr> Vector(Itr first, Itr last) : Container<std::vector<T>>(first, last) {}
Vector(const std::initializer_list<T>& v) : Container<std::vector<T>>(v) {}
Vector(int n, Input& in) : Container<std::vector<T>>(n, in) {}
Vector operator+=(const Vector& v) {
for (int i = 0; i < this->size(); ++i) (*this)[i] += v[i];
return *this;
}
Vector operator+=(const T& v) {
for (auto& i : *this) {
i += v;
}
return *this;
}
Vector operator-=(const Vector& v) {
for (int i = 0; i < this->size(); ++i) (*this)[i] -= v[i];
return *this;
}
Vector operator*=(const Vector& v) {
for (int i = 0; i < this->size(); ++i) (*this)[i] *= v[i];
return *this;
}
Vector operator/=(const Vector& v) {
for (int i = 0; i < this->size(); ++i) (*this)[i] /= v[i];
return *this;
}
Vector operator%=(const Vector& v) {
for (int i = 0; i < this->size(); ++i) (*this)[i] %= v[i];
return *this;
}
bool operator<(const Vector& v) const {
if (this->size() != v.size()) return this->size() < v.size();
for (int i = 0; i < this->size(); ++i) {
if ((*this)[i] != v[i]) {
return (*this)[i] < v[i];
}
}
return false;
}
T inner_product(const Vector<T>& v) const {
return std::inner_product(this->begin(), this->end(), v.begin(), T(0));
}
void output(std::string sep = "\n", std::string end = "\n") const {
if (!this->empty()) {
cout << (*this)[0];
}
for (int i = 1; i < this->size(); ++i) {
cout << sep << (*this)[i];
}
cout << end;
}
Vector<T> partial_sort(int k, bool reverse = false) {
if (!reverse) {
std::partial_sort(this->begin(), this->begin() + k, this->end());
} else {
std::partial_sort(this->begin(), this->begin() + k, this->end(), std::greater<T>());
}
return *this;
}
Vector<T> sort() {
std::sort(this->begin(), this->end());
return *this;
}
Vector<T> rsort() {
std::sort(this->rbegin(), this->rend());
return *this;
}
Vector<T> subvector(int a) const {
return Vector<T>(this->begin(), this->begin() + a);
}
Vector<T> subvector(int a, int b) const {
return Vector<T>(this->begin() + a, this->begin() + b);
}
template<typename Function> auto transform(Function func) const {
Vector<decltype(func(T()))> res;
std::transform(this->begin(), this->end(), std::back_inserter(res), func);
return res;
}
Vector<T> partial_sum() const {
Vector<T> res;
std::partial_sum(this->begin(), this->end(), std::back_inserter(res));
return res;
}
Vector<T> reverse() {
std::reverse(this->begin(), this->end());
return *this;
}
template<typename Function> bool all_of(Function func) {
return std::all_of(this->begin(), this->end(), func);
}
Vector<T> adjacent_difference() const {
Vector<T> res;
std::adjacent_difference(this->begin(), this->end(), std::back_inserter(res));
return res;
}
T lower_bound(T t) const {
return std::lower_bound(this->begin(), this->end(), t) - this->begin();
}
T accumulate() const {
return std::accumulate(this->begin(), this->end(), T(0));
}
template<typename S, typename Function> S accumulate(S n, Function func) const {
return std::accumulate(this->begin(), this->end(), n, func);
}
template<typename Int> static Vector<T> makeVector(Int n) {
return Vector<T>(n);
}
template<typename Int> static Vector<T> makeVector(Input& in, Int n) {
return Vector<T>(n, in);
}
template<typename Int, typename... Ints> static auto makeVector(Input& in, Int n, Ints... ints) {
Vector<decltype(makeVector(in, ints...))> res;
for (int i = 0; i < n; ++i) {
res.emplace_back(makeVector(in, ints...));
}
return res;
}
template<typename Int, typename... Ints> static auto makeVector(Int n, Ints... ints) {
Vector<decltype(makeVector(ints...))> res;
for (int i = 0; i < n; ++i) {
res.emplace_back(makeVector(ints...));
}
return res;
}
Vector<T> unique() {
this->erase(std::unique(this->begin(), this->end()), this->end());
return *this;
}
};
template<typename T> Vector<T> iota(int n, T m = 0) {
Vector<T> v(n);
std::iota(v.begin(), v.end(), m);
return v;
}
/*************************/
/* cumulative_sum_2D.hpp */
/*************************/
template<class Value> class CumulativeSum2D {
private:
struct RangeValue {
int i, j, y, x;
Value v;
RangeValue(int i, int j, int y, int x, Value v) : i(i), j(j), y(y), x(x), v(v) {}
};
Vector<Vector<Value>> val;
Vector<RangeValue> rangeValue;
public:
CumulativeSum2D() {}
CumulativeSum2D(int n, int m) : val(n + 1, Vector<Value>(m + 1, Value(0))) {}
template<typename T> CumulativeSum2D(T v) {
int n = v.size();
int m = v.front().size();
for (int i = 0; i < n + 1; ++i) val.emplace_back(m + 1, Value(0));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
val[i + 1][j + 1] = val[i][j + 1] + val[i + 1][j] - val[i][j] + v[i][j];
}
}
}
void add(int i, int j, Value v) {
add(i, j, i + 1, j + 1, v);
}
void add(int i, int j, int y, int x, Value v) {
rangeValue.emplace_back(i, j, y, x, v);
}
// [(i,j), (y,x))
Value sum(int i, int j, int y, int x) {
if (!rangeValue.empty()) {
int n = val.size() - 1;
int m = val.front().size() - 1;
for (int k = 0; k < 2; ++k) {
for (int i = n - 1; i >= 0; --i) {
for (int j = m - 1; j >= 0; --j) {
val[i + 1][j + 1] -= val[i][j + 1] + val[i + 1][j] - val[i][j];
}
}
}
for (const auto& v : rangeValue) {
val[v.i + 1][v.j + 1] += v.v;
if (v.y < n) val[v.y + 1][v.j + 1] -= v.v;
if (v.x < m) val[v.i + 1][v.x + 1] -= v.v;
if (v.y < n && v.x < m) val[v.y + 1][v.x + 1] += v.v;
}
for (int k = 0; k < 2; ++k) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
val[i + 1][j + 1] += val[i][j + 1] + val[i + 1][j] - val[i][j];
}
}
}
rangeValue.clear();
}
return val[y][x] - val[i][x] - val[y][j] + val[i][j];
}
Value value(int i, int j) {
return sum(i, j, i + 1, j + 1);
}
};
/************/
/* main.cpp */
/************/
int main() {
int n(in);
auto d = Vector<int>::makeVector(in, n, n);
CumulativeSum2D<int> cumulativeSum2D(d);
Vector<int> res(n * n + 1, 0);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
for (int k = i + 1; k <= n; ++k) {
for (int l = j + 1; l <= n; ++l) {
int area = (k - i) * (l - j);
res[area] = max(res[area], cumulativeSum2D.sum(i, j, k, l));
}
}
}
}
for (int i = 0; i < n * n; ++i) {
chmax(res[i + 1], res[i]);
}
int q(in);
for (int i = 0; i < q; ++i) {
cout << res[int(in)] << endl;
}
}
Submission Info
Submission Time |
|
Task |
D - おいしいたこ焼きの焼き方 |
User |
not |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
14058 Byte |
Status |
AC |
Exec Time |
12 ms |
Memory |
256 KB |
Judge Result
Set Name |
Subtask1 |
Subtask2 |
Score / Max Score |
50 / 50 |
50 / 50 |
Status |
|
|
Set Name |
Test Cases |
Subtask1 |
sub0.txt, sub1.txt, sub2.txt, sub_rand_max0.txt, sub_rand_max1.txt, sub_rand_max2.txt, sub_rand_max3.txt, sub_rand_min0.txt, s1.txt, s2.txt, sub0.txt, sub1.txt, sub2.txt, sub_rand_max0.txt, sub_rand_max1.txt, sub_rand_max2.txt, sub_rand_max3.txt, sub_rand_min0.txt |
Subtask2 |
rand0.txt, rand1.txt, rand2.txt, rand3.txt, rand4.txt, rand_max0.txt, rand_max1.txt, rand_max2.txt, rand_max3.txt, rand_max4.txt, s1.txt, s2.txt, sub0.txt, sub1.txt, sub2.txt, sub_rand_max0.txt, sub_rand_max1.txt, sub_rand_max2.txt, sub_rand_max3.txt, sub_rand_min0.txt |
Case Name |
Status |
Exec Time |
Memory |
rand0.txt |
AC |
5 ms |
256 KB |
rand1.txt |
AC |
5 ms |
256 KB |
rand2.txt |
AC |
8 ms |
256 KB |
rand3.txt |
AC |
2 ms |
256 KB |
rand4.txt |
AC |
2 ms |
256 KB |
rand_max0.txt |
AC |
12 ms |
256 KB |
rand_max1.txt |
AC |
12 ms |
256 KB |
rand_max2.txt |
AC |
12 ms |
256 KB |
rand_max3.txt |
AC |
12 ms |
256 KB |
rand_max4.txt |
AC |
12 ms |
256 KB |
s1.txt |
AC |
1 ms |
256 KB |
s2.txt |
AC |
1 ms |
256 KB |
sub0.txt |
AC |
1 ms |
256 KB |
sub1.txt |
AC |
1 ms |
256 KB |
sub2.txt |
AC |
1 ms |
256 KB |
sub_rand_max0.txt |
AC |
1 ms |
256 KB |
sub_rand_max1.txt |
AC |
1 ms |
256 KB |
sub_rand_max2.txt |
AC |
1 ms |
256 KB |
sub_rand_max3.txt |
AC |
1 ms |
256 KB |
sub_rand_min0.txt |
AC |
1 ms |
256 KB |