QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#292351#7120. SoccerHaccerKat0 3ms28496kbC++205.9kb2023-12-28 01:45:232023-12-28 01:45:23

Judging History

你现在查看的是测评时间为 2023-12-28 01:45:23 的历史记录

  • [2024-04-28 08:02:17]
  • 管理员手动重测本题所有提交记录
  • 测评结果:0
  • 用时:3ms
  • 内存:28496kb
  • [2023-12-28 01:45:23]
  • 评测
  • 测评结果:0
  • 用时:3ms
  • 内存:28496kb
  • [2023-12-28 01:45:23]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
template<typename T>
int SIZE(T (&t)){
    return t.size();
}

template<typename T, size_t N>
int SIZE(T (&t)[N]){
    return N;
}

string to_string(char t){
    return "'" + string({t}) + "'";
}

string to_string(bool t){
    return t ? "true" : "false";
}

string to_string(const string &t, int x1=0, int x2=1e9){
    string ret = "";
    for(int i = min(x1,SIZE(t)), _i = min(x2,SIZE(t)-1); i <= _i; ++i){
        ret += t[i];
    }
    return '"' + ret + '"';
}

string to_string(const char* t){
    string ret(t);
    return to_string(ret);
}

template<size_t N>
string to_string(const bitset<N> &t, int x1=0, int x2=1e9){
    string ret = "";
    for(int i = min(x1,SIZE(t)); i <= min(x2,SIZE(t)-1); ++i){
        ret += t[i] + '0';
    }
    return to_string(ret);
}

template<typename T, typename... Coords>
string to_string(const T (&t), int x1=0, int x2=1e9, Coords... C);

template<typename T, typename S>
string to_string(const pair<T, S> &t){
    return "(" + to_string(t.first) + ", " + to_string(t.second) + ")";
}

template<typename T, typename... Coords>
string to_string(const T (&t), int x1, int x2, Coords... C){
    string ret = "[";
    x1 = min(x1, SIZE(t));
    auto e = begin(t);
    advance(e,x1);
    for(int i = x1, _i = min(x2,SIZE(t)-1); i <= _i; ++i){
        ret += to_string(*e, C...) + (i != _i ? ", " : "");
        e = next(e);
    }
    return ret + "]";
}

template<int Index, typename... Ts>
struct print_tuple{
    string operator() (const tuple<Ts...>& t) {
        string ret = print_tuple<Index - 1, Ts...>{}(t);
        ret += (Index ? ", " : "");
        return ret + to_string(get<Index>(t));
    }
};

template<typename... Ts>
struct print_tuple<0, Ts...> {
    string operator() (const tuple<Ts...>& t) {
        return to_string(get<0>(t));
    }
};

template<typename... Ts>
string to_string(const tuple<Ts...>& t) {
    const auto Size = tuple_size<tuple<Ts...>>::value;
    return print_tuple<Size - 1, Ts...>{}(t);
}

void dbgr(){;}
template<typename Heads, typename... Tails>
void dbgr(Heads H, Tails... T){
    cout << to_string(H) << " | ";
    dbgr(T...);
}

void dbgs(){;}
template<typename Heads, typename... Tails>
void dbgs(Heads H, Tails... T){
    cout << H << " ";
    dbgs(T...);
}

/*
formatted functions:
*/

/*
consider __VA_ARGS__ as a whole:
dbgv() prints values only
dbg() prints name and values
*/
#define dbgv(...) cout << to_string(__VA_ARGS__) << endl;

#define dbg(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgv(__VA_ARGS__);
//#define dbg(...)

/*
consider __VA_ARGS__ as a sequence of arguments:
dbgr() prints values only
dbgm() prints names and values
*/
#define dbgr(...) dbgr(__VA_ARGS__); cout << endl;

#define dbgm(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgr(__VA_ARGS__);

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
// using u128 = __uint128_t;
// using i128 = __int128;
const int mod = 1000000007;
const int N = 50;
const int LOG = 20;
const int inf = 1e9;
const double eps = 1e-11;
int n, m, k, qq;
int a[N][N], prefr[N][N], pref[N][N];
int dp[N][N][N][N];
int queryp(int rx, int ry) {
    return (rx < 0 || ry < 0 ? 0 : pref[rx][ry]);
}

int query(int lx, int rx, int ly, int ry) {
    return queryp(rx, ry) - queryp(lx - 1, ry) - queryp(rx, ly - 1) + queryp(lx - 1, ly - 1);
}
    
int dfs(int lx, int rx, int ly, int ry) {
    if (dp[lx][rx][ly][ry] != -1) return dp[lx][rx][ly][ry];
    if (lx > rx || ly < 0 || ry == n || query(lx, rx, ly, ry)) {
        dp[lx][rx][ly][ry] = -inf;
        return -inf;
    }
    
    int x = rx - lx + 1, y = ry - ly + 1;
    dp[lx][rx][ly][ry] = x * y;
    dp[lx][rx][ly][ry] = max(dp[lx][rx][ly][ry], dfs(lx, rx - 1, ly, ry) + y);
    dp[lx][rx][ly][ry] = max(dp[lx][rx][ly][ry], dfs(lx + 1, rx, ly, ry) + y);
    dp[lx][rx][ly][ry] = max(dp[lx][rx][ly][ry], dfs(lx, rx, ly - 1, ry));
    dp[lx][rx][ly][ry] = max(dp[lx][rx][ly][ry], dfs(lx, rx, ly, ry + 1));
    return dp[lx][rx][ly][ry];
}

int biggest_stadium(int N, std::vector<std::vector<int>> F) {
    n = N;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            a[i][j] = F[i][j];
            prefr[i][j] = (j == 0 ? 0 : prefr[i][j - 1]) + a[i][j];
        }
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            pref[i][j] = (i == 0 ? 0 : pref[i - 1][j]) + prefr[i][j];
        }
    }
    
    memset(dp, -1, sizeof(dp));
    int out = 0;
    for (int lx = 0; lx < n; lx++) {
        for (int rx = lx; rx < n; rx++) {
            for (int ly = 0; ly < n; ly++) {
                for (int ry = ly; ry < n; ry++) {
                    out = max(out, dfs(lx, rx, ly, ry));
                }
            }
        }
    }
    
    return out;
}


// void solve() {
//     int N;
//     assert(1 == scanf("%d", &N));
//     std::vector<std::vector<int>> F(N, std::vector<int>(N));
//     for (int i = 0; i < N; i++)
//     {
//         for (int j = 0; j < N; j++)
//         {
//             assert(1 == scanf("%d", &F[i][j]));
//         }
//     }
//     fclose(stdin);

//     int res = biggest_stadium(N, F);

//     printf("%d\n", res);
//     fclose(stdout);
// }


// int32_t main() {
//     std::ios::sync_with_stdio(false);
//     cin.tie(NULL);
//     solve();
// }

详细

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 6
Accepted
time: 0ms
memory: 28212kb

input:

R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L
1
0

output:

xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0
OK
1

result:

ok ok

Test #2:

score: 1.5
Acceptable Answer
time: 0ms
memory: 28496kb

input:

R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L
3
0 0 0
0 1 0
0 0 0

output:

xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0
OK
1433181650

result:

points 0.250 partial

Test #3:

score: 0
Runtime Error

input:

R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L
100
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:


result:


Subtask #2:

score: 0
Wrong Answer

Test #10:

score: 2
Acceptable Answer
time: 3ms
memory: 28496kb

input:

R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L
3
0 0 0
0 1 0
0 1 1

output:

xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0
OK
32756

result:

points 0.250 partial

Test #11:

score: 2
Acceptable Answer
time: 0ms
memory: 28204kb

input:

R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L
3
0 0 0
0 1 1
0 0 1

output:

xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0
OK
32670

result:

points 0.250 partial

Test #12:

score: 2
Acceptable Answer
time: 0ms
memory: 28260kb

input:

R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L
3
0 0 1
0 0 0
1 1 0

output:

xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0
OK
32669

result:

points 0.250 partial

Test #13:

score: 8
Accepted
time: 0ms
memory: 28240kb

input:

R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L
3
1 0 0
1 0 1
0 0 1

output:

xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0
OK
4

result:

ok ok

Test #14:

score: 2
Acceptable Answer
time: 0ms
memory: 28216kb

input:

R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L
3
0 0 1
0 0 0
1 0 0

output:

xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0
OK
762326497

result:

points 0.250 partial

Test #15:

score: 0
Wrong Answer
time: 0ms
memory: 28496kb

input:

R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L
3
0 0 1
0 0 1
0 0 0

output:

xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0
OK
32731

result:

wrong answer wrong

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%