stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include<bits/stdc++.h>

#define N 100005

using namespace std;

char s[N];

int n,a[N],cnt=1,last=1,fa=1;

int main()

{

    scanf("%s",s+1);

    n=strlen(s+1);

    for (int i=1;i<=n;i++) a[i]=s[i]-'0';

    for (int i=1;i<=n-1;i++) if (a[i]^a[n-i]==1) {printf("-1");return 0;}

    if (a[1]==0 || a[n]==1) {printf("-1");return 0;}

    for (int i=2;i<=n/2;i++)

    {

        if (a[i]==1)

        {

            printf("%d %d\n",fa,++cnt);

            int it=cnt;

            for (int j=last+2;j<=i;j++) printf("%d %d\n",it,++cnt);

            last=i,fa=it;

        }

    }

    int it=++cnt;

    printf("%d %d\n",it,fa);

    for (int i=cnt+1;i<=n;i++)

    {

        printf("%d %d\n",it,i);

    }

    return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

using namespace std;

const int maxn = 1e5 + 7;

char s[maxn];

int main(){

    scanf("%s", s+1);

    int len = strlen(s+1);

    if(s[1] != '1' || s[len] != '0'){

        printf("-1\n");

        return 0;

    }

    for(int i = 1; i <= len/2; ++i){

        if(s[i] != s[len-i]){

            printf("-1\n");

            return 0;

        }

    }

    int record = -1;

    for(int i = len/2; i >= 1; --i){

        if(s[i] == '1'){

            record = i;

            printf("%d %d\n", i, i+1);

            for(int j = i+2; j <= len; ++j){

                printf("%d %d\n", i+1, j);

            }

            break;

        }

    }

    for(int i = record-1; i >= 1; --i){

        printf("%d %d\n", record, i);

        if(s[i] == '1'){

            record = i;

        }

    }

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

#define N 100010

int i,j,k,m,n,x,t,y,vis[N],a[N];

char s[N];

int main() {

    scanf("%s", s + 1);

    n = strlen(s + 1);

    for (i = 1; i <= n; ++i)vis[i] = (s[i] == '1');

    if (!vis[1] || !vis[n - 1] || vis[n])return puts("-1"), 0;

    for (i = 2; i < n - 1; ++i)if (vis[i] != vis[n - i])return puts("-1"), 0;

    for (x = 0, i = 1; i <= n; ++i) {

        if (vis[i])while (x > 0)printf("%d %d\n", a[x--], i);

        if (i != n)a[++x] = i;

    }

    while (x > 0)printf("%d %d\n", a[x--], n);

}


// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

using namespace std;

const int maxn = 1e5 + 7;

char s[maxn];

int main(){

    scanf("%s", s+1);

    int len = strlen(s+1);

    if(s[1] != '1' || s[len] != '0'){

        printf("-1\n");

        return 0;

    }

    for(int i = 1; i <= len/2; ++i){

        if(s[i] != s[len-i]){

            printf("-1\n");

            return 0;

        }

    }

    int record = -1;

    for(int i = len/2; i >= 1; --i){

        if(s[i] == '1'){

            record = i;

            printf("%d %d\n", i, i+1);

            for(int j = i+2; j <= len; ++j){

                printf("%d %d\n", i+1, j);

            }

            break;

        }

    }

    for(int i = record-1; i >= 1; --i){

        printf("%d %d\n", record, i);

        if(s[i] == '1'){

            record = i;

        }

    }

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



vector<int> tree[101010];

void dfs(int u, int p){

    for(int i=0;i<tree[u].size();i++){

        int v = tree[u][i];

        if(v != p){

            cout<<u<<" "<<v<<endl;

            dfs(v, u);

        }

    }

}

int main(){

    string s;

    cin>>s;

    int n = s.length();

    s = " " + s;

    if(s[1] == '0' || s[n - 1] == '0' || s[n] == '1')return cout<<-1<<endl, 0;



    int root;

    for(int i=2;i<=n;i++){

        if(i < n && s[i] != s[n - i])return cout<<-1<<endl, 0;

        if(s[i] == '1'){

            root = i;

            for(int j=i-1;j>=1;j--){

                tree[i].push_back(j);

                tree[j].push_back(i);

                if(s[j] == '1')break;

            }

        }

    }

    for(int i=1;i<=n;i++){

        if(tree[i].size() == 0){

            tree[i].push_back(root);

            tree[root].push_back(i);

        }

    }

    dfs(n, -1);

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

string s;

int main(){

    cin >> s;

    int n = s.size();

    s = " " + s;

    if(s[1] == '0' || s[n] == '1')return cout << -1 << endl, 0;

    for(int i = 1; i < n; i++){

        if(s[i] != s[n - i])

            return cout << -1 << endl, 0;

    }



    int cur = 1;

    for(int i = 2; i <= n; i++){

        cout << cur << " " << i << endl;

        if(s[i - 1] == '1'){

            cur = i;

        }

    }

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

#define ll long long int

#include <ext/pb_ds/assoc_container.hpp> 

#include <ext/pb_ds/tree_policy.hpp> 

using namespace __gnu_pbds;   

#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 

#define ld long double

#define ff first

#define ss second

#define pb push_back

#define mp make_pair

#define all(a) a.begin(),a.end()

#define sz(a) (ll)(a.size())

const int M=1e5+5;

std::vector<int> vtr[M];

set<int> st;

ll dfs(int x)

{

	int sb = 1;

	for(auto u:vtr[x])

		sb = sb + dfs(u);

	// cout<<sb<<endl;

	st.insert(sb);

	return sb;

}

int main()

{

	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

	string s;

	cin>>s;

	s = "#"+s;

	int n=sz(s)-1;

	if(s[n]=='1' || s[1]=='0')

	{

		cout<<"-1\n";

		return 0;

	}

	for(int i=1;i<n;i++)

	{

		if(s[i]!=s[n-i])

		{

			cout<<"-1\n";

			return 0;

		}

	}

	for(int i=1;i<=n-1;i++)

	{

		if(s[i]=='0')

			continue;

		int j=i+1;

		while(j<n-1 && s[j]=='0')

			j++;

		for(int k=i;k<j;k++)

		{

			vtr[j].pb(k);

		}

	}

	dfs(n);

	for(int i=1;i<n;i++)

	{

		if(s[i]=='1')

		{

			if(st.find(i)==st.end())

			{

				cout<<"-1\n";

				return 0;

			}

		}

		else

		{

			if(st.find(i)!=st.end() || st.find(n-i)!=st.end())

			{

				cout<<"-1\n";

				return 0;

			}

		}



	}

	for(int i=1;i<=n;i++)

	{

		for(auto u:vtr[i])

			cout<<i<<" "<<u<<"\n";

	}

	return 0;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

#define ll long long int

#include <ext/pb_ds/assoc_container.hpp> 

#include <ext/pb_ds/tree_policy.hpp> 

using namespace __gnu_pbds;   

#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 

#define ld long double

#define ff first

#define ss second

#define pb push_back

#define mp make_pair

#define all(a) a.begin(),a.end()

#define sz(a) (ll)(a.size())

int main()

{

	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

	string s;

	cin>>s;

	s = "#"+s;

	int n=sz(s)-1;

	if(s[n]=='1' || s[1]=='0')

	{

		cout<<"-1\n";

		return 0;

	}

	for(int i=1;i<n;i++)

	{

		if(s[i]!=s[n-i])

		{

			cout<<"-1\n";

			return 0;

		}

	}

	for(int i=1;i<=n-1;i++)

	{

		if(s[i]=='0')

			continue;

		int j=i+1;

		while(j<n-1 && s[j]=='0')

			j++;

		for(int k=i;k<j;k++)

		{

			cout<<j<<" "<<k<<"\n";

		}

	}

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

char ch[100010];

int n,x,pos,cnt=0;

int lian[100010],head[100010];

struct node{

	int to,nxt,cap;

}e[200010];

void add(int u,int v){

	e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;

}

int main(){

	scanf("%s",ch+1);

	n=strlen(ch+1);

	int i,j;

	for(i=1;i<=n;++i)  lian[i]=ch[i]-48;

	if(lian[n]!=0 || lian[1]==0){printf("-1\n");return 0;}

	for(i=1;i<=n;++i){

		if(lian[i]^lian[n-i]){printf("-1\n");return 0;}

	}

	x=(n+1)/2;pos=x+1;

	for(i=pos+1;i<=n;++i)  add(pos,i);

	for(i=x;i>=1;--i){

		add(pos,i);

		if(lian[i])  pos=i;

	}

	for(j=1;j<=n;++j){

		for(i=head[j];i;i=e[i].nxt){

			printf("%d %d\n",j,e[i].to);

		}

	}

	return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#define reg register

using namespace std;

typedef long long ll;

const int MN=1e5+5;

int n,x[MN],y[MN];

char ch[MN];

int main(){

	scanf("%s",ch+1);n=strlen(ch+1);

	if((ch[n]^48)||!(ch[1]^48))return 0*puts("-1");

	for(reg int i=1;i<=(n>>1);i++)if(ch[i]^ch[n-i])return 0*puts("-1");

	reg int pre=1;

	for(reg int i=2;i<=n;i++)if(ch[i]^48)for(;pre<i;pre++)printf("%d %d\n",pre,i);

	printf("%d %d\n",n-1,n);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <cstdio>

#include <set>

#include <cstring>



using std::set;



int u[101000], v[101000], tot = 0;

char c[101000];

set<int> st;



void dfs(int x, int siz)

{

	int rt = x;

	siz--; x++;

	while(1)

	{

		set<int>::iterator it = st.lower_bound(siz); 

		if(st.size() == 0 || (it == st.begin() && (*it) != siz)) break;

		if((*it) != siz) --it;

		u[++tot] = rt; v[tot] = x;

		int new_rt = x;

		x += (*it); siz -= (*it);

		st.erase(it);

		dfs(new_rt, (*it));

	}

	while(siz) u[++tot] = rt, v[tot] = x, x++, siz--;

}

int main()

{

	scanf("%s", c + 1);

	int n = strlen(c + 1);

	for(int i = 1; i <= (n >> 1); i++)

	{

		if(c[i] != c[n - i]) return 0 * puts("-1");

	}

	if(c[1] != '1' || c[n] == '1') return 0 * puts("-1");

	for(int i = 2; i <= (n >> 1); i++) if(c[i] == '1') st.insert(i);

	dfs(1, n);

	if(st.size() != 0) return 0 * puts("-1");

	for(int i = 1; i < n; i++) printf("%d %d\n", u[i], v[i]);

	return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <cstring>

#define fail return puts("-1"), 0



const int N = 1e5 + 5;



char s[N];



int main() {

	scanf("%s", s + 1);

	int n = strlen(s + 1);

	if (s[1] == '0' || s[n] == '1') fail;

	for (int i = 1; i < n; i++) {

		if (s[i] != s[n - i]) fail;

	}

	for (int i = 2, r = 1; i <= n; i++) {

		printf("%d %d\n", r, i);

		if (s[i - 1] == '1') r = i;

	}

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
// in the name of Allah ;

#include<bits/stdc++.h>

using namespace std ;

const int maxn = 1e5 + 10 ;

string s ;

vector < pair < int , int > > ans ;

int n ;

bool valid () 

{

	for ( int i = 0 ; i < n-1 ; i++ ) 

	{

		if ( s[i] != s[n-2-i] ) 

			return false ;

	}

	if ( s[0] != '1' || s[n-1]!= '0' ) 

		return false ; 

	return true ;

}

int main () 

{

	cin>> s ;

	n = s.size() ;

	if ( !valid () ) 

	{

		cout << -1 << endl;

		return 0 ;

	}

	int p = 0 ; 

	for ( int i = 0 ; i < n-1 ; i++ ) 

		if ( s[i] == '1' ) 

			ans.push_back ( { p , i+1 } ) , p = i+1  ;

		else

			 ans.push_back ( { p , i+1} )   ;

	for ( auto tmp : ans ) 

		cout << tmp.first+1 << " " << tmp.second+1 << endl;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <cstring>

#define fail return puts("-1"), 0



const int N = 1e5 + 5;



char s[N];



int main() {

	scanf("%s", s + 1);

	int n = strlen(s + 1);

	if (s[1] == '0' || s[n] == '1') fail;

	for (int i = 1; i < n; i++) {

		if (s[i] != s[n - i]) fail;

	}

	for (int i = 2, r = 1; i <= n; i++) {

		printf("%d %d\n", r, i);

		if (s[i - 1] == '1') r = i;

	}

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



const int N = 1e5 + 10;



char s[N];



int main(){

	int n, flag, now;

	scanf("%s", s + 1);

	n = strlen(s + 1);

	if (s[n] == '1'){

		printf("-1\n");

		return 0;

	} 

	if (s[1] == '0' || s[n - 1] == '0'){

		printf("-1\n");

		return 0;

	}

	flag = 1;

	for (int i = 1; i <= (n - 1) / 2; i++){

		if (s[i] != s[n - i]){

			flag = 0;

			break;

		}

	}

	if (!flag){

		printf("-1\n");

		return 0;

	}

	now = 1;

	for (int i = 1; i <= n / 2; i++){

		printf("%d %d\n", now, i + 1);

		if (s[i] == '1') now = i + 1;

	}

	for (int i = n / 2 + 2; i <= n; i++) printf("%d %d\n", now, i);

	return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <cstring>

#define fail return puts("-1"), 0



const int N = 1e5 + 5;



char s[N];



int main() {

	scanf("%s", s + 1);

	int n = strlen(s + 1);

	if (s[1] == '0' || s[n] == '1') fail;

	for (int i = 1; i < n; i++) {

		if (s[i] != s[n - i]) fail;

	}

	for (int i = 2, r = 1; i <= n; i++) {

		printf("%d %d\n", r, i);

		if (s[i - 1] == '1') r = i;

	}

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <cstring>

using namespace std;



int main(){

  int n,mp[302][302],x[302][302]={},y[302][302]={};

  cin>>n;

  for(int i=0;i<n;i++)

    for(int j=0;j<n;j++)cin>>y[i][j],mp[i][j]=x[i][j]=y[i][j];

  

  int ans=max(y[0][n-1],y[n-1][0]);

  for(int i=0;i<n;i++)

    for(int j=n-2;j>=0;j--) {

      x[i][j]+=x[i][j+1];

      y[j][i]+=y[j+1][i];

      if(ans<x[i][j])ans=x[i][j];

      if(ans<y[j][i])ans=y[j][i];

    }





  int sum[302][302],K[2][302][302]={};





  for(int i=0;i<=n;i++)

    for(int j=0;j<=n;j++) sum[i][j]=-100000000;



  int t=0;

  while(1){

    t++;

    for(int i=0;i<n;i++) //yoko

      for(int j=i+1;j<n;j++) {//yoko

	int a=K[t%2][i][j];

	K[(t+1)%2][i][j]=a;

	sum[i][j]=-100000000;

	for(int k=a+1;k<n;k++) { //tate

	  int X=(x[a][i]-x[a][j+1])+(x[k][i]-x[k][j+1]);

	  int Y=(y[a+1][i]-y[k][i])+(y[a+1][j]-y[k][j]);

	  if(sum[i][j]<=X+Y)sum[i][j]=X+Y,K[(t+1)%2][i][j]=k;

	  ans=max(ans,sum[i][j]);

	}

      }



    int f=1;

    for(int i=0;i<n;i++) //yoko

      for(int j=i+1;j<n;j++) //yoko

	for(int k=K[t%2][i][j]+1;k<K[(t+1)%2][i][j];k++){

	  f=0;

	  int X=(x[k][i+1]-x[k][j])-(x[k-1][i]-x[k-1][j+1]);

	  sum[i][j]+=X;

	  ans=max(ans,sum[i][j]);

	}

    if(f)break;

  }

  cout <<ans<<endl;

	  

  return 0; 

}

// Optimized solution to the same problem (faster):
#include <iostream>

#define INF 10000000

using namespace std;



int main(){

  int n,x[302][302]={},y[302][302]={};

  cin>>n;

  for(int i=0;i<n;i++)

    for(int j=0;j<n;j++)cin>>y[i][j],x[i][j]=y[i][j];



  /*  for(int i=0;i<300;i++)

    for(int j=0;j<300;j++) y[i][j]=x[i][j]=-1;

    n=300;*/

  

  for(int i=0;i<n;i++)

    for(int j=n-2;j>=0;j--) {

      x[i][j]+=x[i][j+1];

      y[j][i]+=y[j+1][i];

    }



  int ans=max(y[0][n-1],y[n-1][0]),sum,K[302][302]={},t=0,f=1;

  while(f){

    t++,f=0;

    for(int i=0;i<n;i++) //yoko

      for(int j=i+1;j<n;j++) {//yoko

	int a=K[i][j],nk=a;

	sum=-INF;

	for(int k=a+1;k<n;k++) { //tate

	  int X=(x[a][i]-x[a][j+1])+(x[k][i]-x[k][j+1]);

	  int Y=(y[a+1][i]-y[k][i])+(y[a+1][j]-y[k][j]);

	  if(sum<=X+Y)sum=X+Y,nk=k;

	}

	ans=max(ans,sum);

	

	if(nk!=n-1)f=1;

	for(int k=a+1;k<nk;k++){//tate

	  sum+=(x[k][i+1]-x[k][j])-(x[k-1][i]-x[k-1][j+1]);

	  ans=max(ans,sum);

	  }

	K[i][j]=nk;

      }

  }

  cout <<ans<<endl;

	  

  return 0; 

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <cstring>

using namespace std;



int main(){

  int n,x[302][302]={},y[302][302]={};

  cin>>n;

  for(int i=0;i<n;i++)

    for(int j=0;j<n;j++)cin>>y[i][j],x[i][j]=y[i][j];

  

  int ans=max(y[0][n-1],y[n-1][0]);

  for(int i=0;i<n;i++)

    for(int j=n-2;j>=0;j--) {

      x[i][j]+=x[i][j+1];

      y[j][i]+=y[j+1][i];

      ans=max(ans,max(y[j][i],x[i][j]));

    }



  int sum[302][302],K[2][302][302]={};

  for(int i=0;i<=n;i++)

    for(int j=0;j<=n;j++) sum[i][j]=-100000000;





  int t=0,f=1;

  while(f){

    t++,f=0;



    for(int i=0;i<n;i++) //yoko

      for(int j=i+1;j<n;j++) {//yoko

	int a=K[t%2][i][j];

	K[(t+1)%2][i][j]=a;

	sum[i][j]=-100000000;

	for(int k=a+1;k<n;k++) { //tate

	  int X=(x[a][i]-x[a][j+1])+(x[k][i]-x[k][j+1]);

	  int Y=(y[a+1][i]-y[k][i])+(y[a+1][j]-y[k][j]);

	  if(sum[i][j]<=X+Y)sum[i][j]=X+Y,K[(t+1)%2][i][j]=k;

	  ans=max(ans,sum[i][j]);

	}

	if(K[t%2][i][j]!=n-1)f=1;

	for(int k=K[t%2][i][j]+1;k<K[(t+1)%2][i][j];k++){//tate

	  sum[i][j]+=(x[k][i+1]-x[k][j])-(x[k-1][i]-x[k-1][j+1]);

	  ans=max(ans,sum[i][j]);

	}

      }

  }

  cout <<ans<<endl;

	  

  return 0; 

}

// Optimized solution to the same problem (faster):
#include <iostream>

#define INF 10000000

using namespace std;



int main(){

  int n,x[302][302]={},y[302][302]={};

  cin>>n;

  for(int i=0;i<n;i++)

    for(int j=0;j<n;j++)cin>>y[i][j],x[i][j]=y[i][j];



  /*  for(int i=0;i<300;i++)

    for(int j=0;j<300;j++) y[i][j]=x[i][j]=-1;

    n=300;*/

  

  for(int i=0;i<n;i++)

    for(int j=n-2;j>=0;j--) {

      x[i][j]+=x[i][j+1];

      y[j][i]+=y[j+1][i];

    }



  int ans=max(y[0][n-1],y[n-1][0]),sum,K[302][302]={},t=0,f=1;

  while(f){

    t++,f=0;

    for(int i=0;i<n;i++) //yoko

      for(int j=i+1;j<n;j++) {//yoko

	int a=K[i][j],nk=a;

	sum=-INF;

	for(int k=a+1;k<n;k++) { //tate

	  int X=(x[a][i]-x[a][j+1])+(x[k][i]-x[k][j+1]);

	  int Y=(y[a+1][i]-y[k][i])+(y[a+1][j]-y[k][j]);

	  if(sum<=X+Y)sum=X+Y,nk=k;

	}

	ans=max(ans,sum);

	

	if(nk!=n-1)f=1;

	for(int k=a+1;k<nk;k++){//tate

	  sum+=(x[k][i+1]-x[k][j])-(x[k-1][i]-x[k-1][j+1]);

	  ans=max(ans,sum);

	  }

	K[i][j]=nk;

      }

  }

  cout <<ans<<endl;

	  

  return 0; 

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

using namespace std;



int main(){

  int n,x[302][302]={},y[302][302]={};

  cin>>n;

  for(int i=0;i<n;i++)

    for(int j=0;j<n;j++)cin>>y[i][j],x[i][j]=y[i][j];

  

  int ans=max(y[0][n-1],y[n-1][0]);

  for(int i=0;i<n;i++)

    for(int j=n-2;j>=0;j--) {

      x[i][j]+=x[i][j+1];

      y[j][i]+=y[j+1][i];

      ans=max(ans,max(y[j][i],x[i][j]));

    }



  

  int sum[302][302],K[2][302][302]={},t=0,f=1;

  while(f){

    t++,f=0;

    for(int i=0;i<n;i++) //yoko

      for(int j=i+1;j<n;j++) {//yoko

	int a=K[t%2][i][j],&b=K[(t+1)%2][i][j];



	b=a;

	sum[i][j]=-10000000;



	for(int k=a+1;k<n;k++) { //tate

	  int X=(x[a][i]-x[a][j+1])+(x[k][i]-x[k][j+1]);

	  int Y=(y[a+1][i]-y[k][i])+(y[a+1][j]-y[k][j]);

	  if(sum[i][j]<=X+Y)sum[i][j]=X+Y,b=k;

	}

	

	if(b!=n-1)f=1;

	ans=max(ans,sum[i][j]);

	for(int k=a+1;k<b;k++){//tate

	  sum[i][j]+=(x[k][i+1]-x[k][j])-(x[k-1][i]-x[k-1][j+1]);

	  ans=max(ans,sum[i][j]);

	}

      }

  }

  cout <<ans<<endl;

	  

  return 0; 

}

// Optimized solution to the same problem (faster):
#include <iostream>

#define INF 10000000

using namespace std;



int main(){

  int n,x[302][302]={},y[302][302]={};

  cin>>n;

  for(int i=0;i<n;i++)

    for(int j=0;j<n;j++)cin>>y[i][j],x[i][j]=y[i][j];



  /*  for(int i=0;i<300;i++)

    for(int j=0;j<300;j++) y[i][j]=x[i][j]=-1;

    n=300;*/

  

  for(int i=0;i<n;i++)

    for(int j=n-2;j>=0;j--) {

      x[i][j]+=x[i][j+1];

      y[j][i]+=y[j+1][i];

    }



  int ans=max(y[0][n-1],y[n-1][0]),sum,K[302][302]={},t=0,f=1;

  while(f){

    t++,f=0;

    for(int i=0;i<n;i++) //yoko

      for(int j=i+1;j<n;j++) {//yoko

	int a=K[i][j],nk=a;

	sum=-INF;

	for(int k=a+1;k<n;k++) { //tate

	  int X=(x[a][i]-x[a][j+1])+(x[k][i]-x[k][j+1]);

	  int Y=(y[a+1][i]-y[k][i])+(y[a+1][j]-y[k][j]);

	  if(sum<=X+Y)sum=X+Y,nk=k;

	}

	ans=max(ans,sum);

	

	if(nk!=n-1)f=1;

	for(int k=a+1;k<nk;k++){//tate

	  sum+=(x[k][i+1]-x[k][j])-(x[k-1][i]-x[k-1][j+1]);

	  ans=max(ans,sum);

	  }

	K[i][j]=nk;

      }

  }

  cout <<ans<<endl;

	  

  return 0; 

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

using namespace std;



int main(){

  int n,x[302][302]={},y[302][302]={};

  cin>>n;

  for(int i=0;i<n;i++)

    for(int j=0;j<n;j++)cin>>y[i][j],x[i][j]=y[i][j];

  

  int ans=max(y[0][n-1],y[n-1][0]);

  for(int i=0;i<n;i++)

    for(int j=n-2;j>=0;j--) {

      x[i][j]+=x[i][j+1];

      y[j][i]+=y[j+1][i];

    }



  

  int sum[302][302],K[2][302][302]={},t=0,f=1;

  while(f){

    t++,f=0;

    for(int i=0;i<n;i++) //yoko

      for(int j=i+1;j<n;j++) {//yoko

	int a=K[t%2][i][j],&b=K[(t+1)%2][i][j];

	b=a+1;

	sum[i][j]=-10000000;



	for(int k=a+1;k<n;k++) { //tate

	  int X=(x[a][i]-x[a][j+1])+(x[k][i]-x[k][j+1]);

	  int Y=(y[a+1][i]-y[k][i])+(y[a+1][j]-y[k][j]);

	  if(sum[i][j]<=X+Y)sum[i][j]=X+Y,b=k;

	}

	

	if(b<=n-1)f=1;

	ans=max(ans,sum[i][j]);

	for(int k=a+1;k<b;k++){//tate

	  sum[i][j]+=(x[k][i+1]-x[k][j])-(x[k-1][i]-x[k-1][j+1]);

	  ans=max(ans,sum[i][j]);

	}

      }

  }

  cout <<ans<<endl;

	  

  return 0; 

}

// Optimized solution to the same problem (faster):
#include <iostream>

#define INF 10000000

using namespace std;



int main(){

  int n,x[302][302]={},y[302][302]={};

  cin>>n;

  for(int i=0;i<n;i++)

    for(int j=0;j<n;j++)cin>>y[i][j],x[i][j]=y[i][j];



  /*  for(int i=0;i<300;i++)

    for(int j=0;j<300;j++) y[i][j]=x[i][j]=-1;

    n=300;*/

  

  for(int i=0;i<n;i++)

    for(int j=n-2;j>=0;j--) {

      x[i][j]+=x[i][j+1];

      y[j][i]+=y[j+1][i];

    }



  int ans=max(y[0][n-1],y[n-1][0]),sum,K[302][302]={},t=0,f=1;

  while(f){

    t++,f=0;

    for(int i=0;i<n;i++) //yoko

      for(int j=i+1;j<n;j++) {//yoko

	int a=K[i][j],nk=a;

	sum=-INF;

	for(int k=a+1;k<n;k++) { //tate

	  int X=(x[a][i]-x[a][j+1])+(x[k][i]-x[k][j+1]);

	  int Y=(y[a+1][i]-y[k][i])+(y[a+1][j]-y[k][j]);

	  if(sum<=X+Y)sum=X+Y,nk=k;

	}

	ans=max(ans,sum);

	

	if(nk!=n-1)f=1;

	for(int k=a+1;k<nk;k++){//tate

	  sum+=(x[k][i+1]-x[k][j])-(x[k-1][i]-x[k-1][j+1]);

	  ans=max(ans,sum);

	  }

	K[i][j]=nk;

      }

  }

  cout <<ans<<endl;

	  

  return 0; 

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#define INF 10000000

using namespace std;



int main(){

  int n,x[302][302]={},y[302][302]={};

  cin>>n;

  for(int i=0;i<n;i++)

    for(int j=0;j<n;j++)cin>>y[i][j],x[i][j]=y[i][j];

  

  for(int i=0;i<n;i++)

    for(int j=n-2;j>=0;j--) {

      x[i][j]+=x[i][j+1];

      y[j][i]+=y[j+1][i];

    }



  int ans=max(y[0][n-1],y[n-1][0]),sum[302][302],K[2][302][302]={},t=0,f=1;

  while(f){

    t++,f=0;

    for(int i=0;i<n;i++) //yoko

      for(int j=i+1;j<n;j++) {//yoko

	int a=K[t%2][i][j],&b=K[(t+1)%2][i][j];

	b=a;

	sum[i][j]=-INF;



	for(int k=a+1;k<n;k++) { //tate

	  int X=(x[a][i]-x[a][j+1])+(x[k][i]-x[k][j+1]);

	  int Y=(y[a+1][i]-y[k][i])+(y[a+1][j]-y[k][j]);

	  if(sum[i][j]<=X+Y)sum[i][j]=X+Y,b=k;

	}

	ans=max(ans,sum[i][j]);



	if(b!=n-1)f=1;

	for(int k=a+1;k<b;k++){//tate

	  sum[i][j]+=(x[k][i+1]-x[k][j])-(x[k-1][i]-x[k-1][j+1]);

	  ans=max(ans,sum[i][j]);

	}

      }

  }

  cout <<ans<<endl;

	  

  return 0; 

}

// Optimized solution to the same problem (faster):
#include <iostream>

#define INF 10000000

using namespace std;



int main(){

  int n,x[302][302]={},y[302][302]={};

  cin>>n;

  for(int i=0;i<n;i++)

    for(int j=0;j<n;j++)cin>>y[i][j],x[i][j]=y[i][j];



  /*  for(int i=0;i<300;i++)

    for(int j=0;j<300;j++) y[i][j]=x[i][j]=-1;

    n=300;*/

  

  for(int i=0;i<n;i++)

    for(int j=n-2;j>=0;j--) {

      x[i][j]+=x[i][j+1];

      y[j][i]+=y[j+1][i];

    }



  int ans=max(y[0][n-1],y[n-1][0]),sum,K[302][302]={},t=0,f=1;

  while(f){

    t++,f=0;

    for(int i=0;i<n;i++) //yoko

      for(int j=i+1;j<n;j++) {//yoko

	int a=K[i][j],nk=a;

	sum=-INF;

	for(int k=a+1;k<n;k++) { //tate

	  int X=(x[a][i]-x[a][j+1])+(x[k][i]-x[k][j+1]);

	  int Y=(y[a+1][i]-y[k][i])+(y[a+1][j]-y[k][j]);

	  if(sum<=X+Y)sum=X+Y,nk=k;

	}

	ans=max(ans,sum);

	

	if(nk!=n-1)f=1;

	for(int k=a+1;k<nk;k++){//tate

	  sum+=(x[k][i+1]-x[k][j])-(x[k-1][i]-x[k-1][j+1]);

	  ans=max(ans,sum);

	  }

	K[i][j]=nk;

      }

  }

  cout <<ans<<endl;

	  

  return 0; 

}

// Fastest known solution for this problem: