JOI本選で大コケしました

1番でグローバル変数じゃないとMLEするのに気づけなかったのが主な敗因

問１ーグローバル変数でとらないとMLE

#include <string>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <iostream>
#include <map>

using namespace std;
typedef long long LL;

int memo[1000+1][1000+1][3];

int main()
{
	int h,w;
	cin >> h >> w;
	int time;
	cin >> time;

	char star[1000][1000];
	for(int i=0;i<h;i++)
		scanf("%s",star[i]);

	for(int y=0;y<=h;y++)
		for(int x=0;x<=w;x++)
			memo[y][x][0]=memo[y][x][1]=memo[y][x][2]=0;

	for(int y=1;y<=h;y++)
		for(int x=1;x<=w;x++)
		{
			memo[y][x][0]=memo[y][x-1][0];
			memo[y][x][1]=memo[y][x-1][1];
			memo[y][x][2]=memo[y][x-1][2];

			if(star[y-1][x-1]=='J')
				memo[y][x][0]++;
			if(star[y-1][x-1]=='O')
				memo[y][x][1]++;
			if(star[y-1][x-1]=='I')
				memo[y][x][2]++;
		}

	for(int y=1;y<=h;y++)
	{
		for(int x=1;x<=w;x++)
		{
			memo[y][x][0]+=memo[y-1][x][0];
			memo[y][x][1]+=memo[y-1][x][1];
			memo[y][x][2]+=memo[y-1][x][2];
		}
	}

	for(time;0<time;time--)
	{
		int l,r,b,c;
		cin >> b >> l >> c >> r;

		int J=0,O=0,I=0;
		J=(memo[c][r][0]-memo[b-1][r][0]-memo[c][l-1][0]+memo[b-1][l-1][0]);
		O=(memo[c][r][1]-memo[b-1][r][1]-memo[c][l-1][1]+memo[b-1][l-1][1]);
		I=(memo[c][r][2]-memo[b-1][r][2]-memo[c][l-1][2]+memo[b-1][l-1][2]);

		cout << J << " " << O << " " << I << endl;
	}
	return 0;
}

問２ーメモ化再帰

#include <vector>
#include <algorithm>
#include <functional>
#include <stdio.h>

using namespace std;

vector<vector<int> > book(10);
int cache[10][2000];

int rec(int g,int left)
{
	if(10<=g)
		return 0;
	if(cache[g][left]!=-1)
		return cache[g][left];

	int r=0;
	for(int num=0;num<=left;num++)
	{
		if(book[g].size()<num)
			continue;
		int a=0;
		for(int i=0;i<num;i++)
			a+=(book[g][i]+num-1);
		r=max(a+rec(g+1,left-num),r);
	}
	//printf("cache[%d][%d]=%d\n",g,left,r);
	return cache[g][left]=r;
}

int main()
{
	for(int i=0;i<10;i++)
		for(int j=0;j<2000;j++)
			cache[i][j]=-1;

	int N,K;
	scanf("%d %d",&N,&K);
	for(int i=0;i<N;i++)
	{
		int c,g;
		scanf("%d %d",&c,&g);
		g--;
		book[g].push_back(c);
	}
	for(int i=0;i<10;i++)
		sort(book[i].begin(),book[i].end(),greater<int>());

	int ans=rec(0,K);
	printf("%d\n",ans);
	return 0;
}

問３ーダイクストラだったらしい

#include <iostream>
#include <queue>
#include <vector>
#include <cstdio>

using namespace std;

class EDGE
{
	public:
		int to,cost;

		bool operator<(const EDGE &e)
		const{
			return (cost>e.cost);
		}
};

class BRANCH
{
	public:
		int left,right,length;
};

int main()
{
	int N,M,K;
	cin >> N >> M >> K;

	vector<vector<EDGE> > G(N);
	vector<int> dist(N,(1<<28));
	priority_queue<EDGE> que;
	vector<BRANCH> branch;

	for(int i=0;i<M;i++)
	{
		int a,b,c;
		cin >> a >> b >> c;
		a--,b--;

		EDGE e;
		e.to=b,e.cost=c;
		G[a].push_back(e);
		e.to=a,e.cost=c;
		G[b].push_back(e);

		BRANCH br;
		br.left=a,br.right=b,br.length=c;
		branch.push_back(br);
	}

	for(int i=0;i<K;i++)
	{
		int a;
		cin >> a;
		a--;

		EDGE e;
		e.to=a,e.cost=0;
		que.push(e);
	}

	while(!que.empty())
	{
		int t=que.top().to,c=que.top().cost;
		que.pop();
		
		if(dist[t]<=c)
			continue;

		dist[t]=c;

		for(int i=0;i<(int)G[t].size();i++)
		{
			EDGE e;
			e.to=G[t][i].to;
			e.cost=G[t][i].cost+c;
			que.push(e);
		}
	}

	int ans=0;
	for(int i=0;i<M;i++)
	{
		int a=dist[branch[i].left]+branch[i].length+dist[branch[i].right];
		a+=(a%2==1) ? 1 : 0;
		a/=2;
		ans=max(ans,a);
	}

	cout << ans << endl;
}

問４ーソートして真ん中から

#include <algorithm>
#include <vector>
#include <iostream>
#include <utility>
#include <cstdio>
#define MAX_V 100010

typedef long long LL;
using namespace std;

LL ABS(LL num)
{
	return (num<0) ? -num : num;
}

LL xPos[MAX_V];
LL yPos[MAX_V];
pair<LL,LL> house[MAX_V];

int main()
{
	int W,H,N,xN,yN;
	cin >> W >> H >> N;

	for(int i=0;i<N;i++)
	{
		cin >> xPos[i] >> yPos[i];
		house[i]=make_pair(xPos[i],yPos[i]);
	}
	sort(xPos,xPos+N);
	//xN=unique(xPos,xPos+N)-xPos;
	sort(yPos,yPos+N);
	//yN=unique(yPos,yPos+N)-yPos;
	xN=yN=N;

	//printf("xPos.size()=%d yPos.size()=%d\n",xPos.size(),yPos.size());

	vector<LL> xCord;
	vector<LL> yCord;

	for(int i=max(0,xN/2-10);i<min(xN,xN/2+10);i++)
		xCord.push_back(xPos[i]);
	for(int i=max(0,yN/2-10);i<min(yN,yN/2+10);i++)
		yCord.push_back(yPos[i]);
	sort(xCord.begin(),xCord.end());
	sort(yCord.begin(),yCord.end());

	LL ansX=0;
	LL ansY=0;
	LL ansDist=((LL)1<<50);

	for(int i=0;i<(int)xCord.size();i++)
		for(int j=0;j<(int)yCord.size();j++)
		{
			LL x=xCord[i];
			LL y=yCord[j];
			LL maxD=0;
			LL dist=0;

			//printf("x=%lld y=%lld\n",x,y);

			for(int k=0;k<N;k++)
			{
				LL d=ABS(house[k].first-x)+ABS(house[k].second-y);
				maxD=max(d,maxD);
				dist+=d*2;
			}
			dist-=maxD;
			if(dist<ansDist)
			{
				ansDist=dist;
				ansX=x;
				ansY=y;
			}
		}

	cout << ansDist << endl;
	cout << ansX << " " << ansY << endl;

	return 0;
}