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
AC × 22
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