Submission #26217

#	Time	Username	Problem	Language	Result	Execution time	Memory
26217		imsifile	Abduction 2 (JOI17_abduction2)	C++14	44 / 100	4703 ms	16712 KiB

abduction2

#include<stdio.h>
#include<algorithm>
#include<map>
using namespace std;

typedef long long lld;

int H, W, Q;
int ho[150505], ver[150505];
map<pair<int,int>, lld> vd, hd;

lld verti(int, int);
lld hori(int, int);

lld verti(int h, int v){
	int gap = vd[make_pair(h,v)];
	if(gap) return gap;
	int val = ver[v];
	int i;
	lld up=0, down=0;
	for(i=h+1; i<H; i++){
		up=i-h;
		if(ho[i]>val)break;
	}
	if(i<H) up += hori(v, i);
	for(i=h-1; i>=0; i--){
		down=h-i;
		if(ho[i]>val)break;
	}
	if(i>=0) down += hori(v, i);
	return vd[make_pair(h,v)] = max(up, down);
}

lld hori(int v, int h){
	int gap = hd[make_pair(h,v)];
	if(gap) return gap;
	int val = ho[h];
	int i;
	lld up=0, down=0;
	for(i=v+1; i<W; i++){
		up=i-v;
		if(ver[i]>val)break;
	}
	if(i<W) up += verti(h, i);
	for(i=v-1; i>=0; i--){
		down=v-i;
		if(ver[i]>val)break;
	}
	if(i>=0) down += verti(h, i);
	return hd[make_pair(h,v)]=max(up, down);
}

int main(){
	scanf("%d%d%d", &H, &W, &Q);
	for(int i=0; i<H; i++) scanf("%d", &ho[i]);
	for(int i=0; i<W; i++) scanf("%d", &ver[i]);
	while(Q--){
		int h, v;
		scanf("%d%d", &h, &v), h--, v--;
		printf("%lld\n", max(verti(h, v), hori(v, h)));
	}
	return 0;
}

Compilation message (stderr)

abduction2.cpp: In function 'int main()':
abduction2.cpp:54:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &H, &W, &Q);
                             ^
abduction2.cpp:55:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<H; i++) scanf("%d", &ho[i]);
                                            ^
abduction2.cpp:56:45: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<W; i++) scanf("%d", &ver[i]);
                                             ^
abduction2.cpp:59:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &h, &v), h--, v--;
                                  ^

• Subtask 1: 13 / 13
• Subtask 2: 10 / 10
• Subtask 3: 17 / 17
• Subtask 4: 4 / 4
• Subtask 5: 0 / 56