Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 我N^3也过了，贴代码

Posted by cavatina2016 at 2020-09-07 09:53:13 on Problem 3351
```#include <stdlib.h>
#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAX_N	1000
#define MAX_M	10
#define MAX_K	20

int N, M, K;
int A[MAX_N][MAX_M];
int results[MAX_N][MAX_N];
int sums[MAX_M];
bool datas[MAX_N][MAX_N];
int maxvalue1, maxvalue2;
int maxleft1, maxright1;
int maxleft2, maxright2;

void S(unsigned long long* arr, int idx)
{
arr[idx / 64] |= (1ULL << (idx % 64));
}

bool And(unsigned long long* arr1, unsigned long long* arr2, int start, int end)
{
int s = start / 64, e = end / 64;

for (int i = s; i <= e; ++i) {
if (arr1[i] & arr2[i]) return true;
}
return false;
}

int calc()
{
K = N / 64 + 2;

for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
sums[j] = 0;
}
for (int j = i; j < N; ++j) {
for (int k = 0; k < M; ++k) {
sums[k] += A[j][k];
}
int m = INT_MIN, idx = -1;
for (int k = 0; k < M; ++k) {
if (sums[k] >= m) {
m = sums[k];
idx = k;
}
}
datas[i][j] = idx == 0;
}
}

for (int i = 0; i < N; ++i) {
results[0][i] = datas[i][N - 1] ? 1 : -1;
}

for (int i = 0; i < N; ++i) {
for (int j = i; j < N; ++j) {
if (datas[i][j]) {
}
}
}

for (int i = 1; i < N; ++i) {
maxvalue1 = maxvalue2 = INT_MIN;

for (int j = N - 1 - i; j >= 0; --j) {
int x = results[i - 1][j + 1];
if (x > maxvalue1) {
maxvalue2 = maxvalue1;
maxleft2 = maxleft1;
maxright2 = maxright1;

maxvalue1 = x;
maxleft1 = maxright1 = j;
}
else if (x == maxvalue1) {
maxleft1 = j;
}
else if (x > maxvalue2) {
maxvalue2 = x;
maxleft2 = maxright2 = j;
}
else if (x == maxvalue2) {
maxleft2 = j;
}

results[i][j] = maxvalue1 + 1;
}
else {
results[i][j] = max(maxvalue1 - 1, maxvalue2 + 1);
}
else {
results[i][j] = maxvalue1 - 1;
}
}
}
}

for (int i = N - 1; i >= 0; --i) {
if (results[i][0] > 0) {
return N - i - 1;
}
}
return -1;
}

int main()
{
scanf_s("%d %d", &N, &M);
while (N < 2 || N > MAX_N || M < 2 || M > MAX_M) printf("...");

for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
scanf_s("%d", &A[i][j]);
}
}

printf("%d\n", calc());
return 0;
}```

Followed by: