Submission #3779596
Source Code Expand
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define REVERSE(a) reverse(a.begin(), a.end())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define int long long
#define INF 1000000000000000000
using namespace std;
#define ANS(f) if(f) cout << "YES" << endl; else cout << "NO" << endl;
typedef vector<int> vec;
typedef vector<vec> mat;
typedef pair<int, int> Pii;
template<typename T>
void readv(vector<T> &a){ REP(i, a.size()) cin >> a[i]; }
void readi(vector<int> &a){ REP(i, a.size()){cin >> a[i]; a[i]--;} }
void debug(mat m){REP(i, m.size()){ REP(j, m[i].size()){ cout << m[i][j] << ","; } cout << endl; }}
class RMQ_segment_tree
{
using data_type = Pii;
public:
vector<data_type> dat;
int N;
data_type inf;
RMQ_segment_tree(int n, data_type inf): inf(inf) {
N = 1;
while(n > N) N = N << 1;
dat = vector<data_type>(2 * N - 1, inf);
}
//k番目の値をaに更新
void update(int k, data_type a){
k += N - 1;
dat[k] = a;
while(k > 0){
k = (k - 1) / 2;
dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]);
}
}
//[a, b)の最小値
data_type minval(int a, int b){
return query(a, b, 0, 0, N);
}
data_type query(int a, int b, int k, int l, int r){
if(r <= a || b <= l) return inf;
if(a <= l && r <= b) return dat[k];
else{
data_type vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
data_type vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
return min(vl, vr);
}
}
};
void addm(mat &m, RMQ_segment_tree &ST, int a, int b){
if(a == b) return;
Pii p = ST.minval(a, b);
int v = p.first, i = p.second;
m[a][i] -= v;
m[i + 1][i] += v;
m[a][b] += v;
m[i + 1][b] -= v;
addm(m, ST, a, i);
addm(m, ST, i + 1, b);
}
signed main(){
int N, M; cin >> N >> M;
vec A(N - 1); readv(A);
mat B(N, vec(M));
REP(i, N) readv(B[i]);
mat m(N + 1, vec(N + 1, 0));
REP(i, M){
RMQ_segment_tree ST(N, Pii(INF, INF));
REP(j, N) ST.update(j, Pii(-B[j][i], j));
addm(m, ST, 0, N);
}
REP(a, N + 1) REP(b, N) m[a][b + 1] += m[a][b];
REP(b, N + 1) REP(a, N) m[a + 1][b] += m[a][b];
//debug(m);
vec sumA(N);
sumA[0] = 0;
REP(i, N - 1) sumA[i + 1] = sumA[i] + A[i];
int ans = 0;
REP(a, N){
FOR(b, a, N){
ans = max(ans, m[a][b] - sumA[b] + sumA[a]);
}
}
cout << ans;
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Yakiniku Restaurants |
User |
sumitacchan |
Language |
C++14 (GCC 5.4.1) |
Score |
1000 |
Code Size |
2950 Byte |
Status |
AC |
Exec Time |
1508 ms |
Memory |
206208 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1000 / 1000 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt |
All |
sample_01.txt, sample_02.txt, subtask_1_dense_max_01.txt, subtask_1_dense_max_02.txt, subtask_1_dense_max_03.txt, subtask_1_dense_max_04.txt, subtask_1_dense_rand_01.txt, subtask_1_dense_rand_02.txt, subtask_1_dense_rand_03.txt, subtask_1_dense_rand_04.txt, subtask_1_max_01.txt, subtask_1_max_02.txt, subtask_1_max_03.txt, subtask_1_max_04.txt, subtask_1_min_01.txt, subtask_1_min_02.txt, subtask_1_rand_01.txt, subtask_1_rand_02.txt, subtask_1_rand_03.txt, subtask_1_rand_04.txt, subtask_1_widemax_01.txt, subtask_1_widemax_02.txt, subtask_1_widemax_03.txt, subtask_1_widemax_04.txt, subtask_1_widemax_05.txt, subtask_1_widemax_06.txt, subtask_1_widemax_07.txt, subtask_1_widemax_08.txt, subtask_1_widemax_09.txt, subtask_1_widemax_10.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
1 ms |
256 KB |
sample_02.txt |
AC |
1 ms |
256 KB |
subtask_1_dense_max_01.txt |
AC |
1468 ms |
204160 KB |
subtask_1_dense_max_02.txt |
AC |
1463 ms |
204160 KB |
subtask_1_dense_max_03.txt |
AC |
1467 ms |
204160 KB |
subtask_1_dense_max_04.txt |
AC |
1467 ms |
204160 KB |
subtask_1_dense_rand_01.txt |
AC |
768 ms |
100736 KB |
subtask_1_dense_rand_02.txt |
AC |
870 ms |
113792 KB |
subtask_1_dense_rand_03.txt |
AC |
26 ms |
5248 KB |
subtask_1_dense_rand_04.txt |
AC |
179 ms |
31616 KB |
subtask_1_max_01.txt |
AC |
1470 ms |
204160 KB |
subtask_1_max_02.txt |
AC |
1464 ms |
204160 KB |
subtask_1_max_03.txt |
AC |
1467 ms |
204160 KB |
subtask_1_max_04.txt |
AC |
1467 ms |
204160 KB |
subtask_1_min_01.txt |
AC |
1 ms |
256 KB |
subtask_1_min_02.txt |
AC |
1 ms |
256 KB |
subtask_1_rand_01.txt |
AC |
114 ms |
8704 KB |
subtask_1_rand_02.txt |
AC |
130 ms |
28544 KB |
subtask_1_rand_03.txt |
AC |
147 ms |
17920 KB |
subtask_1_rand_04.txt |
AC |
837 ms |
173568 KB |
subtask_1_widemax_01.txt |
AC |
1472 ms |
204160 KB |
subtask_1_widemax_02.txt |
AC |
1508 ms |
204160 KB |
subtask_1_widemax_03.txt |
AC |
1468 ms |
204160 KB |
subtask_1_widemax_04.txt |
AC |
1469 ms |
204160 KB |
subtask_1_widemax_05.txt |
AC |
1466 ms |
204160 KB |
subtask_1_widemax_06.txt |
AC |
1462 ms |
204160 KB |
subtask_1_widemax_07.txt |
AC |
1453 ms |
206208 KB |
subtask_1_widemax_08.txt |
AC |
1464 ms |
204160 KB |
subtask_1_widemax_09.txt |
AC |
1489 ms |
204160 KB |
subtask_1_widemax_10.txt |
AC |
1464 ms |
204160 KB |