Submission #697446
Source Code Expand
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
using namespace std;
#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define snuke(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
typedef long long ll;
#define INF (1ll<<60)
int A,B;
ll a[2010],b[2010];
ll sa[2010],sb[2010];
ll amax[2010][2010],bmax[2010][2010];
int K;
ll x[2010],y[2010];
void add_point(ll px, ll py){
while(1){
if(K < 2) break;
ll dx1 = x[K-1] - x[K-2], dx2 = px - x[K-2];
ll dy1 = y[K-1] - y[K-2], dy2 = py - y[K-2];
if(dx1 * dy2 > dx2 * dy1) K--; else break;
}
x[K] = px;
y[K] = py;
K++;
}
ll func(ll xc, ll yc){
int low = 0, high = K-1;
while(high - low > 2){
int d = (high - low) / 3;
int l = low + d;
int r = high - d;
if(xc * x[l] + yc * y[l] > xc * x[r] + yc * y[r]) high = r; else low = l;
}
ll ans = -INF;
for(int i=low;i<=high;i++) ans = max(ans, x[i] * xc + y[i] * yc);
return ans;
}
ll query(int X, int Y){
int i,j;
ll ans = -INF;
// for(i=1;i<=X;i++) for(j=1;j<=Y;j++) ans = max(ans, i * bmax[Y][j] + j * amax[X][i]);
K = 0;
for(i=1;i<=X;i++) add_point(i, amax[X][i]);
for(j=1;j<=Y;j++) ans = max(ans, func(bmax[Y][j], j));
return ans;
}
int main(void){
int i,j;
cin >> A >> B;
REP(i,A) cin >> a[i];
REP(i,B) cin >> b[i];
REP(i,A) sa[i+1] = sa[i] + a[i];
REP(i,B) sb[i+1] = sb[i] + b[i];
REP(i,A+1) REP(j,A+1) amax[i][j] = -INF;
REP(i,A+1) REP(j,A+1){
if(i > 0) amax[i][j] = max(amax[i][j], amax[i-1][j]);
if(i-j >= 0) amax[i][j] = max(amax[i][j], sa[i] - sa[i-j]);
}
REP(i,B+1) REP(j,B+1) bmax[i][j] = -INF;
REP(i,B+1) REP(j,B+1){
if(i > 0) bmax[i][j] = max(bmax[i][j], bmax[i-1][j]);
if(i-j >= 0) bmax[i][j] = max(bmax[i][j], sb[i] - sb[i-j]);
}
int Q;
cin >> Q;
REP(i,Q){
int X,Y;
cin >> X >> Y;
ll ans = query(X, Y);
cout << ans << endl;
}
return 0;
}
Submission Info
Submission Time |
|
Task |
D - 長方形 |
User |
chokudai |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
2241 Byte |
Status |
AC |
Exec Time |
505 ms |
Memory |
63232 KB |
Judge Result
Set Name |
all |
Score / Max Score |
100 / 100 |
Status |
|
Set Name |
Test Cases |
all |
amax_0.txt, amax_1.txt, amax_2.txt, example_0.txt, example_1.txt, example_2.txt, manyneg_0.txt, manyneg_1.txt, manyneg_2.txt, maxrand_0.txt, maxrand_1.txt, maxrand_2.txt, random_0.txt, random_1.txt, random_2.txt, random_3.txt, random_4.txt, smallrand_0.txt, smallrand_1.txt, smallrand_2.txt, smallrand_3.txt, smallrand_4.txt |
Case Name |
Status |
Exec Time |
Memory |
amax_0.txt |
AC |
501 ms |
63232 KB |
amax_1.txt |
AC |
505 ms |
63232 KB |
amax_2.txt |
AC |
504 ms |
63232 KB |
example_0.txt |
AC |
4 ms |
256 KB |
example_1.txt |
AC |
4 ms |
256 KB |
example_2.txt |
AC |
4 ms |
384 KB |
manyneg_0.txt |
AC |
479 ms |
63232 KB |
manyneg_1.txt |
AC |
465 ms |
63232 KB |
manyneg_2.txt |
AC |
455 ms |
63232 KB |
maxrand_0.txt |
AC |
480 ms |
63232 KB |
maxrand_1.txt |
AC |
467 ms |
63232 KB |
maxrand_2.txt |
AC |
453 ms |
63232 KB |
random_0.txt |
AC |
79 ms |
35072 KB |
random_1.txt |
AC |
89 ms |
37632 KB |
random_2.txt |
AC |
143 ms |
36608 KB |
random_3.txt |
AC |
154 ms |
30080 KB |
random_4.txt |
AC |
120 ms |
35968 KB |
smallrand_0.txt |
AC |
4 ms |
384 KB |
smallrand_1.txt |
AC |
4 ms |
256 KB |
smallrand_2.txt |
AC |
4 ms |
384 KB |
smallrand_3.txt |
AC |
5 ms |
384 KB |
smallrand_4.txt |
AC |
6 ms |
384 KB |