akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

const long long mod =1e+7 ;
const int N = 3e3+5;


#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define ll long long
#define fr(i,l,m) for(int i=l;i<m;i++)
# define vii vector<int>
#define vpr vector<pair<ll,ll> >
ll pwr(ll x,ll y);
bool isprime(int n) ;
string s,t,ans="";
int lca[N][N];

int main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);


cin>>s>>t;
int s_sz=s.size(),t_sz=t.size();


fr(i,0,s_sz+1)
{
    fr(j,0,t_sz+1)
    {
        if(i==0 || j==0){lca[i][j]=0;}
        else if(s[i-1]==t[j-1]){lca[i][j]=(1+lca[i-1][j-1]);}
        else
        {
            lca[i][j]=max(lca[i-1][j],lca[i][j-1]);
        }
        //cout<<lca[i][j]<<' ';
    }
  //  cout<<endl;
}

int i=s_sz,j=t_sz;
while(i>0 && j>0)
{

        if(s[i-1]==t[j-1])
        {
            ans+=s[i-1];
            i-=1;j-=1;
        }
        else if(lca[i-1][j]>lca[i][j-1])
        {
            i-=1;

        }
        else
        {
            j-=1;

        }

}

reverse(ans.begin(),ans.end());
cout<<ans<<endl;
return 0;
}
ll pwr(ll x,ll y)
{
    ll ans=1;
    x=x%mod;
    while(y>0){
    if(y&1)ans=(x*(ans%mod))%mod;
    x=(x*x)%mod;
    y=y/2;

    }
    return ans%mod;
}

bool isprime(int n)
{
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
    if (n % 2 == 0 || n % 3 == 0)
        return false;

    for (int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;

    return true;
}


Measured memory_bytes: 35456
S = list(map(int, list(input())))
N = len(S)
MOD = 2019
DP = [0] * MOD
DP[0] = 1

t = 0
p = 1
for i in range(N):
  k = S[-1 - i]
  t = (t + k * p) % MOD
  DP[t] += 1
  p = p * 10 % MOD

ans = 0
for i in range(MOD):
  n = DP[i]
  ans += (n * (n - 1)) // 2

print(ans)

Measured memory_bytes: 86732
a, b = [int(x) for x in input().split()]
 
if (b < a):
    temp = b
    b = a
    a = temp
    
x = 1
while True:
    if (int(x*0.08) == a and int(x*0.1) == b):
        print(x)
        break
    else:
        if (x > 1500):
            print(-1)
            break
        else:
            x += 1

Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int a, b, c, ans = 0;
    cin >> a >> b >> c;
    for (int i = a; i <= b; i++) {
        if (c % i == 0) {
            ans++;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 3096
#![allow(unused_imports, unused_variables, dead_code)]
use std::io::*;
use std::fmt::*;
use std::str::*;
use std::cmp::*;
use std::collections::*;

trait InputValue {
    fn parse(s: &str) -> Self;
}

fn read<T: InputValue>() -> T {
    let mut buf = String::new();
    let _ = stdin().read_line(&mut buf);
    T::parse(&buf.trim())
}

fn readnc<T: InputValue>() -> Vec<T> {
    let mut vec = vec![];
    let line: String = read();
    for token in line.split_whitespace() {
        vec.push(T::parse(token));
    }
    vec
}

fn readn<T: InputValue>(n: usize) -> Vec<T> {
    let mut vec = vec![];
    for _ in 0..n {
        vec.push(read());
    }
    vec
}

macro_rules! parse_single_value {
    ($($t:ty),*) => {
        $(
            impl InputValue for $t {
                fn parse(s: &str) -> $t { s.parse().unwrap() }
            }
        )*
	}
}
parse_single_value!(i32, i64, f32, f64, usize, String);

macro_rules! parse_tuple {
	($($t:ident),*) => {
		impl<$($t),*> InputValue for ($($t),*) where $($t: InputValue),* {
			fn parse(s: &str) -> ($($t),*) {
				let mut tokens = s.split_whitespace();
				let t = ($($t::parse(tokens.next().unwrap())),*);
				t
			}
		}
	}
}
parse_tuple!(A, B);
parse_tuple!(A, B, C);

// ===

const INF: usize = 100000000;
const MAX: usize = 5010;

fn main() {
    let n: usize = read();
    let mut p: Vec<usize> = readnc();
    p.insert(0, n);
    for i in 1..n {
        p[i] -= 1;
    }

    let x: Vec<usize> = readnc();

    let mut children: Vec<Vec<usize>> = vec![vec![]; n];
    for i in 1..n {
        children[p[i]].push(i);
    }


    let mut best: Vec<usize> = vec![INF; n];
    let mut dp: Vec<Vec<usize>> = vec![vec![INF; MAX]; 2];

    let mut isok = true;
    for i in (0..n).rev() {
        let cn = children[i].len();
        for i in 0..MAX {
            dp[0][i] = INF;
            dp[1][i] = INF;
        }

        dp[0][0] = 0;
        for ci in 0..cn {
            let a = x[children[i][ci]];
            let b = best[children[i][ci]];

            let fi = ci % 2;
            let ti = 1 - fi;
            for i in 0..MAX {
                dp[ti][i] = INF;
            }
            for i in 0..MAX {
                if dp[fi][i] == INF {
                    continue
                }
                let base = dp[fi][i];
                let ia = i + a;
                if ia < MAX {
                    dp[ti][ia] = min(dp[ti][ia], base + b);
                }
                let ib = i + b;
                if ib < MAX {
                    dp[ti][ib] = min(dp[ti][ib], base + a);
                }
            }
        }

        let wi = cn % 2;
        let mut best_op = INF;
        for l in 0..x[i]+1 {
            best_op = min(best_op, dp[wi][l]);
        }

        if best_op == INF {
            isok = false;
            break
        }
        best[i] = best_op;
    }

    if isok {
        println!("POSSIBLE");
    } else {
        println!("IMPOSSIBLE");
    }
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
// cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
using namespace std;
#define endl "\n"
const int N = 1e6, inf = 1e9;
typedef long long ll;
#define deb(x) cout << #x << " = " << x << endl;
#define debg cout << "yes" << endl;

#define fast                     \
    ios::sync_with_stdio(false); \
    cin.tie(NULL);               \
    cout.tie(NULL)
#define Test  \
    int t;    \
    cin >> t; \
    while (t--)
#define pb push_back
#define F first
#define S second
#define fo(i, n) for (int i = 0; i < n; i++)
#define fo1(i, b, n) for (int i = b; i < n; i++)
#define fon(i, n) for (int i = n - 1; i >= 0; i--)
#define Ln length()
#define pb push_back
#define mp make_pair
int main()
{
    int x;
    cin>>x;
    if(x==0)cout<<"1"<<endl;
    else puts("0");
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
#define rep(i,n) for (ll i=0; i < (n); ++i)
using namespace std;
typedef long long ll;

ll N,x[100],y[100],h[100],H[100],cx,cy;

bool check(){
    ll j;
    rep(i,N)if(h[i]>0){j=i;break;}
    for(ll i=j;i<N;i++){
        if(H[j] != H[i] && h[i] > 0)return false;
    }
    return true;
}

int main(void){
    cin >> N;
    ll sum=0;
    rep(i,N){
        cin >> x[i] >> y[i] >> h[i];
        sum+=h[i];
    }
    if(sum==1){
        rep(i,N)if(h[i]>0){
            cout << x[i] <<" " <<y[i]<<" "<< h[i] <<endl;
            return 0;
        }
    }
    
    
    rep(cx,101){
        rep(cy,101){
            rep(i,N){
                H[i] = abs(cx-x[i])+abs(cy-y[i])+h[i];
            }
            if(check()){
                ll CH;
                rep(i,N)if(h[i]>0)CH =H[i];
                cout << cx <<" " <<cy <<" " <<CH <<endl;
                return 0;
            }
        }
    }
}


Measured memory_bytes: 256
while True:
    g1=input()
    if g1=="0":
        break
    g2=input()
    g3=input()
    r1a=g1[1:].count("A")
    r1b=g1[1:].count("B")
    if g2[0]=="A":
        r1a+=1
    if g2[0]=="B":
        r1b+=1
    print(r1a,r1b)
    r2a=g2[1:].count("A")
    r2b=g2[1:].count("B")
    if g3[0]=="A":
        r2a+=1
    if g3[0]=="B":
        r2b+=1
    print(r2a,r2b)
    r3a=g3[1:].count("A")
    r3b=g3[1:].count("B")
    if r3a>r3b:
        r3a+=1
    if r3a<r3b:
        r3b+=1
    print(r3a,r3b)


Measured memory_bytes: 5552
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int n,t,a,h;
    cin >> n;
    cin >> t >> a;
    int count=0,res=100000000;

    for(int i=0;i<n;i++){
        cin >> h;
        int temp = abs((t*1000-h*6)-a*1000);
        if(temp<res){
            res = temp;
            count=i;
        }
    }
    cout << count+1 << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <chrono>
#include<math.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std::chrono;
using namespace std;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// declaration: ordered_set os;  methods->  1. *os.find_by_order(x)   2. os.order_of_key(k) ->return int

#define fr(x,i,n) for(int x = i; x < n; ++x)
#define fb(x,i,n) for(int x = i; x >= n; --x)
#define pr pair<int,int>
#define ll long long int
#define ld long double
const ll mod=998244353;


void solve(){
    ll a;
    string s;
    cin>>a>>s;
    ll b=0;
    while(s.length()<4)
    s+='0';
    fr(i,0,s.length()){
        if(s[i]!='.')
        b=b*10+s[i]-'0';
    }
    cout<<(a*b)/100LL;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
//    build();
    int t=1;
//    cin>>t;
    while(t--)
    solve();

}


Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;

int main() {
  string s, t;
  cin>>s>>t;
  int n = s.length();
  int cnt = 0;
  for (int i=0; i<n; i++) {
    if (s[i] != t[i]) {
      ++cnt;
    }
  }
  cout<<cnt<<endl;
}

Measured memory_bytes: 3836
#include <bits/stdc++.h>
using namespace std;

int main() {
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  int sum_l, sum_r;
  sum_l = A + B;
  sum_r = C + D;
  if (sum_l > sum_r){
    cout << "Left" << endl;
  }else if (sum_l < sum_r) {
    cout << "Right" << endl;
  }else{
    cout << "Balanced" << endl;
  }
}

Measured memory_bytes: 384
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        int a = sc.nextInt();
        int b = sc.nextInt();

        String relation;
        if (a < b){
            relation = "<";
        } else if (a > b){
            relation = ">";
        } else{
            relation = "==";
        }
    System.out.printf("a %s b\n", relation);
    }
}



Measured memory_bytes: 26320
#include <iostream>
#include <vector>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main()
{
    int n;
    cin >> n;
    cout << (n + 1) / 2 << endl;
    return 0;
}


Measured memory_bytes: 888
#include <bits/stdc++.h>

typedef long long LL;
typedef unsigned long long ULL;

#define debug printf("fuck %d\n", __LINE__);

inline LL read() {
	LL res = 0, bo = 1; char ch = getchar();
	while(ch < '0' || ch > '9') { if (ch == '-') bo = -1; ch = getchar(); }
	while(ch >= '0' && ch <= '9') { res = (res << 1) + (res << 3) + ch - '0'; ch = getchar(); }
	return bo * res;
}

template<typename T> void read(T &x) { x = read(); }
template<typename T, typename ...Argv> void read(T &a, Argv &...argv) { read(a); read(argv...); }

const int N = 500;
int C[N][N], f[N][N], s[N][N], n, k, p;

int add(int x, int y) { x += y; return x >= p ? x - p : x; }

int main() {
	n = read(), k = read(), p = read(); 
	for (int i = 0; i <= n; ++ i) for (int j = C[i][0] = 1; j <= i; ++ j) C[i][j] = add(C[i - 1][j], C[i - 1][j - 1]);
	for (int i = 0; i <= k; ++ i) f[1][i] = 1, s[1][i] = k - i + 1;
	for (int i = 2; i <= n + 1; ++ i) {
		for (int j = 0; j <= k; ++ j) {
			for (int l = 1; l < i; ++ l) {
				f[i][j] = (f[i][j] + 1LL * s[l][j + 1] * f[i - l][j] % p * C[i - 2][l - 1] % p) % p;
			}
		}
		for (int j = k; j >= 0; -- j) s[i][j] = add(s[i][j + 1], f[i][j]);
	}
	std::cout << f[n + 1][0] << std::endl;
	return 0;
}

Measured memory_bytes: 2048
#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (n); i++)
#define REP(i, init, n) for(int i = init; i < (n); i++)

using namespace std;
using ll = long long int;
using P = pair<int, int>;
using T = tuple<int, int, int>;
using edge = struct
{
    int to, cost;
};

const int MOD = 1e9 + 7;
const int iINF = 1e9;
const long long int llINF = 1e18;
const double PI = acos(-1.0);

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int main()
{
    int N, X, ans = 0;
    cin >> N >> X;
    vector<int> m(N);
    rep(i, N) cin >> m[i];

    X -= accumulate(m.begin(), m.end(), 0);

    sort(m.begin(), m.end());

    ans += X / m[0];

    cout << ans + N << endl;

    
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;

class Progaram
{
    static void Main(string[] args)
    {
        var l = Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToArray();
        l[0] = l[0] % l[1];
        l[1] = l[1] - l[0];
        Console.WriteLine(l.Min());
    }
}

Measured memory_bytes: 13396
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long n = Long.parseLong(sc.next());
		long ans = 0;

		long num = 1;
		while (true) {

			if ((n - num) / num <= num) {
				break;
			}

			if ((n - num) % num == 0) {
				ans += (n - num) / num;
			}
			num++;

		}

		System.out.println(ans);

		sc.close();
	}

}

Measured memory_bytes: 23764
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define REP(i, a, b) for(ll i = a; i < b; i++)
#define out(x) std::cout << x << '\n'
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define sz(x) ((int)(x).size())
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { ll g = gcd(a, b); return a / g * b; }
const int dx[4] = { 1, 0, -1,  0 };
const int dy[4] = { 0, 1,  0, -1 };
const int INF = INT_MAX / 2;
const ll  inf = LLONG_MAX / 2;
const int mod = 1000000007;
const int MAX_N = 101010;
const long double PI = acos(-1);

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(10);
	/*------------------------------*/

	int n;
	cin >> n;

	vector<vector<ll>> num(10, vector<ll>(10, 0));

	for (int i = 1; i <= n; i++) {
		string s = to_string(i);
		int f = s.front() - '0';
		int b = s.back() - '0';
		num[f][b]++;
	}

	ll ans = 0;
	rep(i, 10) {
		rep(j, 10) {
			ans += num[i][j] * num[j][i];
		}
	}

	out(ans);

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
ll INFL = 1000000000000000010;//10^18 = 2^60
int INF = 2147483600;//10^9
ll MOD  = 1000000007;
int dx[4] = {0,0, 1,-1};
int dy[4] = {1,-1,0,0};

int prime[60000];
bool is_Prime[60001];
vector<int> ans(0);
int sieve(int n){
    int p = 0;
    for(int i = 0; i <= n; i++) is_Prime[i] = true;
    is_Prime[0] = is_Prime[1] = false;
    for(int i = 2; i <= n; i++){
        if(is_Prime[i]){
            prime[p++] = i;
            for(int j = 2 * i; j <= n; j += i) is_Prime[j] = false;
        }
    }
    return p;
}
int p;
void solve(){
    int N;
    cin >> N;
    p = sieve(55555);
    for(int i = 0; i < 55555; i++){
        if(is_Prime[i]){
            if(i % 5 == 1) ans.push_back(i);
        }
    }
    for(int i = 0; i < N; i++){
        cout << ans.at(i) << " ";
    }
    cout << endl;
}

int main(void){
    solve();
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
#define sqr(x) ((x)*(x))
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define ld long double
#define vi vector<ll>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define debuge cerr<<"isok"<<endl
#define debug(x) cerr<<#x<<"="<<x<<endl
#define SS second
#define FF first
#define ls (k<<1)
#define rs (k<<1|1)
#define inf 0x3f3f3f3f
#define clr(a,x) memset(a,x,sizeof(a))
#define cpy(a,x) memcpy(a,x,sizeof(a))
#define file(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout);
using namespace std;

const ll bnd=1e9;
const int N=100005,M=100005,mod=1e9+7;
template<class T> inline void gmin(T &x,const T &y){if(x>y) x=y;}
template<class T> inline void gmax(T &x,const T &y){if(x<y) x=y;}
inline void ch(int &x,int y){x=(x+y)%mod;}
template<class T> inline void read(T &x){
	x=0;char ch=getchar();
	while(ch>'9'||ch<'0') ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
}
template<class T> inline void print(T x){
	if(!x){puts("0");return;}
	int a[20],m=0;
	while(x) a[m++]=x%10,x/=10;
	while(m--) putchar(a[m]+'0');puts("");
}
inline int exp(int x,int y){
	int ans=1;
	while(y){
		if(y&1) ans=(ll)ans*x%mod;
		x=(ll)x*x%mod;y>>=1;
	}return ans;
}

int n,a[20],D,t;
ll ans=0;
vi L,R;
ll pw[20];
map<int,int>aa,bb;
void make(int n,int l,int r,bool high,vi &ans){
//	printf("%d %d %d\n",n,l,r);
	ans.clear();
	clr(a,0);
	while(!a[r+1]){
		ll res=0;
		if(high&&!a[r]) goto change;
		for(int i=l;i<=r;i++)
			res+=(ll)a[i]*(pw[n-i]-pw[i]);
		ans.pb(res);
		change:int i=l;
		while(i<=r&&a[i]==9){
			a[i]=0;
			i++;
		}
		a[i]++;
	}
}
ll get(ll D){
	while(D&&D%10==0) D/=10,t++;
	ll ans=0;
	if(!D) ans+=9;
	for(int i=1;i<=10;i++){
		int mid=i/2;
		ll res=0;
		make(i,0,mid,0,L);
		sort(L.begin(),L.end());
		make(i,mid+1,i,1,R);
		sort(R.begin(),R.end());
		for(int j=0;j<L.size();j++){
			int t=upper_bound(R.begin(),R.end(),D-L[j])-lower_bound(R.begin(),R.end(),D-L[j]);
			ans+=t;res+=t;
		}
		if(res) debug(i);
	}
	for(int i=1;i<=t;i++) ans*=10;
	return ans;
}
void dfs(int x,ll now,ll si){
//	if(now<0) return;
	ll t1=now,t2=now;
	for(int j=x;j<=n/2;j++)
		t1+=(pw[n-j]-pw[j])*9,t2-=(pw[n-j]-pw[j])*9;
	if(t1<0||t2>D) return;
	if(n%2==0&&x==n/2){
		if(now==(ll)D) ans+=si*10;
		return;
	}
	if(n%2==1&&x==n/2+1){
		if(now==(ll)D) {if(n%2==0) ans+=si/10; else ans+=si;}
		return;
	}
	for(int i=-9;i<=9;i++)
		if(!x) dfs(x+1,now+(pw[n-x]-pw[x])*i,si*aa[i]); else dfs(x+1,now+(pw[n-x]-pw[x])*i,si*bb[i]);
}

int main(){
#ifdef rqgao2014
	freopen("input.txt","r",stdin);
	srand(time(0));
#endif
	ios::sync_with_stdio(0);
	pw[0]=1;
	for(int i=1;i<=19;i++) pw[i]=pw[i-1]*10;
	aa.clear();bb.clear();
	for(int i=0;i<=9;i++)
		for(int j=0;j<=9;j++){
			if(j) aa[i-j]++;
			bb[i-j]++;
		}
	read(D);
	for(int i=1;i<=18;i++){
		n=i;
		dfs(0,0,1);
	}
	cout<<ans<<endl;
#ifdef rqgao2014
	time_tester(1);
#endif
	return 0;
}




Measured memory_bytes: 256
n = int(input())
eki = []
for i in range(n-1):
    c,s,f = map(int,input().split())
    eki.append([c,s,f])
for i in range(n-1):
    now = eki[i]
    time = now[0] + now[1]
    for j in range(i+1,n-1):
        now = eki[j]
        if time <= now[1]:
            time = now[0]+now[1]
        else:
            if time%now[2] == 0:
                time += now[0]
            else:
                time += now[2] - time%now[2] + now[0]
    print(time)
print(0)

Measured memory_bytes: 3188
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm> 
using namespace std;

int main()
{
	long long n,ans=0;
	cin>>n;
	for(int i=1;i<n;i++)
	{
		for(int j=1;j*i<n;j++)
		{
			ans++;
		}
	}
	cout<<ans;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;

int main() {

	double a, b, x; cin >> a >> b >> x;
	
	if (x == a * a * b) {
		cout << 0 << endl;
		return 0;
	}

	double S = x / a;
	double ans;
	double y;
	if (a * b / 2 < S) {
		double dS = 2 * S - a * b;
		double l = dS / a;
		S -= dS;
		b -= l;
		y = a;		
	}
	else {
		y = 2 * S / b;
	}
	ans = atan(b / y);

	cout << fixed << setprecision(11) << ans * 180 / M_PI << endl;

	return 0;

}

Measured memory_bytes: 256
//#include <bits/stdc++.h>
#include<iostream>
#include<iomanip>
#include<numeric>
#include<cstdio>
#include<cmath>
#include<string>
#include<algorithm>
#include<vector>
#include<utility>
#include<map>
#include<stack>
#include<queue>
#include<ctype.h>
#include <fstream>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
using namespace std;
typedef long long ll;//int64
typedef unsigned long long ull;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
int dy[4]={0,1,0,-1};
//----------program from here----------

int main(){
    ull N=0, count=0, ans=0;
    cin >> N;
    ull A[N];
    for(int i=0; i<N; ++i) cin >> A[i];
    sort(A, A+N);
    for(int i=N-1; i>=0; --i){
        if(A[N-1]%A[i]){
            cout << gcd(A[N-1], A[i]) << endl;
            return 0;
        }
    }
    cout << A[0] << endl;
}

Measured memory_bytes: 1024
/* Dynamic Programming implementation of LCS problem */
#include<iostream> 
#include<cstring> 
#include<cstdlib> 
using namespace std; 

/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
void lcs( string X, string Y, int m, int n ) 
{ 
int L[m+1][n+1]; 

/* Following steps build L[m+1][n+1] in bottom up fashion. Note 
	that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */
for (int i=0; i<=m; i++) 
{ 
	for (int j=0; j<=n; j++) 
	{ 
	if (i == 0 || j == 0) 
		L[i][j] = 0; 
	else if (X[i-1] == Y[j-1]) 
		L[i][j] = L[i-1][j-1] + 1; 
	else
		L[i][j] = max(L[i-1][j], L[i][j-1]); 
	} 
} 

// Following code is used to print LCS 
int index = L[m][n]; 

// Create a character array to store the lcs string 
char lcs[index+1]; 
lcs[index] = '\0'; // Set the terminating character 

// Start from the right-most-bottom-most corner and 
// one by one store characters in lcs[] 
int i = m, j = n; 
while (i > 0 && j > 0) 
{ 
	// If current character in X[] and Y are same, then 
	// current character is part of LCS 
	if (X[i-1] == Y[j-1]) 
	{ 
		lcs[index-1] = X[i-1]; // Put current character in result 
		i--; j--; index--;	 // reduce values of i, j and index 
	} 

	// If not same, then find the larger of two and 
	// go in the direction of larger value 
	else if (L[i-1][j] > L[i][j-1]) 
		i--; 
	else
		j--; 
} 

// Print the lcs 
cout << lcs << endl; 
} 

/* Driver program to test above function */
int main() 
{ 
string X, Y; cin>>X>>Y;
int m = (int)X.size(); 
int n = (int)Y.size(); 
lcs(X, Y, m, n); 
return 0; 
} 


Measured memory_bytes: 35456
#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int n;
  while ( cin >> n, n ) {
    vector<int> dot(n);
    vector<string> str(n);
    vector<string> ans(n);
    
    for ( int i = 0; i < n; i++ ) {
      string s;
      cin >> s;
      int j = 0;
      while ( s[j] == '.' ) j++;
      dot[i] = j;
      str[i] = s.substr(j);
      ans[i] = string(j, ' ');      
    }
    
    for ( int i = 0; i < n; i++ ) {
      if ( dot[i] ) ans[i][dot[i]-1] = '+';
      if ( i == n-1 ) break;
      
      bool flag = false;
      int p = 0;
      for ( int j = i+1; j < n; j++ ) {
	if ( dot[j] <= dot[i] ) break;
	if ( dot[j] == dot[i]+1 ) {
	  flag = true;
	  p = j;
	}
      }

      if ( !flag ) continue;
      
      for ( int j = i+1; j < p; j++ ) {
	ans[j][dot[i]] = '|';
      }
    }

    for ( int i = 0; i < n; i++ ) {
      cout << ans[i]+str[i] << endl;      
    }
  }
  
  return 0;
}



Measured memory_bytes: 3732
#include<iostream>

using namespace std;
int main(){
	
	int W,H,x,y,r;
	cin >> W >> H >> x >> y >> r;

	if(x - r < 0){
		cout << "No"<<endl;
	}
	else if (y - r < 0){
		cout << "No" << endl;
	}
	else if (x + r > W){
		cout << "No" << endl;
	}
	else if (y + r>H){
		cout << "No" << endl;
	}
	else if (x - r >= 0){
		cout << "Yes" << endl;
	}
	else if (x + r <= W){
		cout << "Yes" << endl;
	}
	else if (y - r >= 0){
		cout << "Yes" << endl;
	}
	else if (y + r <= H){
		cout << "Yes" << endl;
	}
	
	return 0;
}


Measured memory_bytes: 3088
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <algorithm>
#include <cstdio>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <fstream>
#include <cmath>

#define ll int64_t
#define Rep(i, n) for (ll i = 0; i < n; i++)
using namespace std;
typedef vector<ll> vec;
typedef vector<vec> mat;

template<class T> inline void chmin(T& a, T b) {
    if (a > b) {
        a = b;
    }
}
template<class T> inline void chmax(T& a, T b) {
    if (a < b) {
        a = b;
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    ofstream w_file("abc145_e.txt", ios::out);

    ll N, T;
    cin >> N >> T;
    vector<pair<ll, ll>> dish(N);
    Rep (i, N) {
        ll A, B;
        cin >> A >> B;
        dish[i] = make_pair(A, B);
    }

    vector<vector<ll>> dp(N+1, vector<ll>(T+1, 0)), dp2(N+1, vec(T+1, 0));
    Rep (i, N) {
        ll a = dish[i].first, b = dish[i].second;
        Rep (j, T+1) {
            chmax(dp[i+1][j], dp[i][j]);
            if (j-a >= 0) {
                chmax(dp[i+1][j-a], dp[i][j] + b);
            }
        }
    }

    for (ll i = N-1; i >= 0; i--) {
        ll a = dish[i].first, b = dish[i].second;
        Rep (j, T+1) {
            chmax(dp2[i][j], dp2[i+1][j]);
            if (j-a >= 0) chmax(dp2[i][j-a], dp2[i+1][j] + b);
        }
    }

    ll ans = 0;
    Rep (i, N) {
        ll tmp = 0;
        Rep (j, T) {
            chmax(tmp, dp[i][T-j] + dp2[i+1][j+1]);
        }
        chmax(ans, tmp + dish[i].second);
    }

    cout << ans << "\n";
}

Measured memory_bytes: 141184
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

x, y = MAP()

if x*y < 0:
	print(1+abs(abs(x)-abs(y)))
elif x == 0 or y == 0:
	if x < y:
		print(max(abs(x), abs(y)))
	else:
		print(1+max(abs(x), abs(y)))
else:
	if y > x:
		print(y-x)
	else:
		print(2+x-y)


Measured memory_bytes: 5196
function Main(input) {
    var N = input;
 
    var a = N.length;
    var ans1=0;
    var ans2=0;
    var mem=0;
    for(var i=0;i<a;i++){
        var b = N.charAt(i);
        if(i%2==0 && b=="1"){
            ans1++;
        }else if(i%2==1 && b=="0"){
            ans1++;
        }
    }
    for(var i=0;i<a;i++){
        var b = N.charAt(i);
        if(i%2==0 && b=="0"){
            ans2++;
        }else if(i%2==1 && b=="1"){
            ans2++;
        }
    }
 
    console.log(Math.min(ans1,ans2));
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7500
X,N = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
nlist = [0 for i in range(105)] 
for i in p:
    nlist[i]=1
for i in range(max(X+1,100-X+1)):
    
    if X-i>=0:
        if nlist[X-i] == 0:
            result = X-i
            break
    if X+i<=101:
        if nlist[X+i] == 0:
            result = X+i
            break
print(result)

Measured memory_bytes: 9204
#include <bits/stdc++.h>
using namespace std;

int main(){
    string s;
    cin >>s ;
for(int i= 0;i<s.length();i++){
   if(i%2==0){
       if(s[i]=='L'){
           cout << "No" << endl;
           return 0;
       }
   }else{
    if(s[i]=='R'){
        cout << "No"<<endl;
        return 0;
    }
}
}
cout << "Yes" << endl;
return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
typedef long long ll;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int W,H;
  cin >> W >> H;
  int p[W],q[H];
  rep(i,W) cin >> p[i];
  rep(i,H) cin >> q[i];
  pair<int, int> cost[W+H];//cost , tate(0) or yoko(1);
  rep(i,W){
    cost[i] = mp(p[i],1);
  }
  rep(i,H){
    cost[i+W] = mp(q[i],0);
  }
  sort(cost, cost+(W+H));
  ll ans=0;
  int num_H=0;
  int num_W=0;
  int num=0;
  rep(i,H+W){
    if(cost[i].second==1){
      num = H + 1 - num_H;
      num_W++;
    }
    else{
      num = W+1-num_W;
      num_H++;
    }
    ans += 1LL*num*cost[i].first;
  }
  cout << ans << endl;
  return 0;
    

}


Measured memory_bytes: 2688
#include<stdio.h>

int main(void){
	int n,m,a[110][110],b[110][1],c[110][1],i,j,sum=0;
	scanf("%d %d",&n,&m);
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			scanf("%d",&a[i][j]);
		}
	}			//??£??????
	for(i=1;i<=m;i++){
		scanf("%d",&b[i][1]);
	}
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			sum+=a[i][j]*b[j][1];
		}
		c[i][1]=sum;
		sum=0;
	}
	for(i=1;i<=n;i++){
		printf("%d\n",c[i][1]);
	}
	return 0;
}

Measured memory_bytes: 648
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<string>
#define rep(i,N) for(int i=0;i<N;i++)

long long  INF=1000000000000000000;
long long mod=1000000007;
using namespace std;

int main(){
int N;
cin>>N;
string ans="No";
rep(i,26){
    rep(k,15){
        if(i*4+k*7==N){
            ans="Yes";
        }
    }

}

cout<<ans<<endl;
 return 0;
}
/*
11

Yes

*/

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cstdio>
#include <algorithm>
#include <functional>

using namespace std;

typedef long long ll;
#define all(x) (x).begin(),(x).end()
#define lim 100010
#define mod 1e9+7
#define INF 1e9
#define REP(i,n) for(int i=0;i<n;i++)

int main() {
    int N;
    scanf("%d",&N);
    int xy[N][2];
    for(int i=0; i<N; i++){
        scanf("%d %d", &xy[i][0], &xy[i][1]);
    }
    double d[N+1][N+1] = {0};
    for(int i = 1; i <= N; i++){
        for (int j = i + 1; j <= N; j++){
            double dx = xy[i-1][0] - xy[j-1][0];
            double dy = xy[i-1][1] - xy[j-1][1];
            d[i][j] = pow(dx*dx + dy*dy, 0.5);
            d[j][i] = d[i][j];
        }
    }


    double sum = 0.0;
    vector<int> v(N);
    for (int i = 0; i < N; i++)v[i] = i + 1;
    do{
        for(int i = 0; i < N - 1; i++){
            sum += d[v[i]][v[i + 1]];
        }
    } while(next_permutation(v.begin(), v.end()));

    int Factorial = 1;
    for(int i = 2; i <= N; i++)Factorial *= i;
    printf("%lf", sum / Factorial);

    return 0;
}

Measured memory_bytes: 256
def main():
    inp_line = input().split()
    
    login_coin = int(inp_line[0])       # ログインの度に得られるコイン
    add_coin = int(inp_line[1])         # 週ボーナスで追加で得られるコイン
    need_coin = int(inp_line[2])        # 少なくとも必要なコインの枚数
    
    # 入力チェック
    if not(1 <= login_coin <= 1000)\
       or not(0 <= add_coin <= 1000)\
       or not(1 <= need_coin <= 10 ** 6):
        print("入力が不正です。")
        return

    login_count = 0
    coin = 0
    while True:
        login_count += 1
        coin += login_coin
        # 7日Login
        if login_count % 7 == 0:
            coin += add_coin

        if coin >= need_coin:
            break

    print(login_count)

main()


Measured memory_bytes: 5600
#![allow(unused_imports)]
#![allow(clippy::many_single_char_names)]
#![allow(clippy::suspicious_arithmetic_impl)]

// using Rust(1.42.0)
// My Library Repo is at "https://github.com/Loptall/prcn_lib"
// check available crates on AtCoder at "https://atcoder.jp/contests/language-test-202001"

/*
    AtCoder Language Update 2020204 お疲れ様でした! 有難いです(p.s. 過去問対応もありがとうございます)
*/

// from std...
use std::cmp::{
    max, min,
    Ordering::{Equal, Greater, Less},
};
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
use std::mem::swap;
use std::ops::*;
use std::usize::{MAX, MIN};
use std::{i128, i16, i32, i64, i8, isize, u128, u16, u32, u64, u8, usize};

// Dep crates are...
use itertools::*;
use itertools_num::*;
use lazy_static::lazy_static;
use maplit::{btreemap, btreeset, hashmap, hashset};
use num_bigint::{BigInt, BigUint};
use num_complex::Complex;
use num_integer::{binomial, gcd, lcm, Integer};
use num_rational::Rational;
use num_traits::{One, Zero};
use permutohedron::Heap;
use petgraph::unionfind::UnionFind;
use proconio::{fastout, input, is_stdin_empty, marker::*};
use rand::random;

// code...
// #[fastout]
fn main() {
    input! {
        a: usize, b: usize
    }

    println!("{}", a * b);
}


Measured memory_bytes: 2080
#include <bits/stdc++.h>

using namespace std;

int n, k;
vector<int> a;
vector<int> dp;

int main(){
    cin>>n>>k;
    a.resize(n); dp.resize(k+1);
    for(int i = 0; i < n; i++){
        cin>>a[i];
    }
    //dp[k] -> 1 means first player win with k
    dp[0] = 0;
    for(int i = 1; i <= k; i++){
        dp[i] = 1;
        for(int j = 0; j < n; j++){
            if(a[j] <= i){
                dp[i] = min(dp[i], dp[i - a[j]]);
            }
        }
        dp[i] = !dp[i];
    }
    int res = dp[k];
    if(res){
        cout<<"First"<<endl;
    }else{
        cout<<"Second"<<endl;
    }
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define modulo 998244353
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 1000000000

int main(){
	
	int N;
	cin>>N;
	
	vector<long long> C(N+1,0);
	
	for(int i=1;i<=N;i++){
		for(int j=i;j<=N;j+=i){
			C[j] ++;
		}
	}
	
	long long ans = 0;
	
	for(int i=1;i<=N;i++){
		ans += C[i] * i;
	}
	
	cout<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 81400
line = input().split(" ")

hp_t = int(line[0])
at_t = int(line[1])
hp_a = int(line[2])
at_a = int(line[3])

hp_now_t = hp_t
hp_now_a = hp_a

while(1):
  hp_now_a = hp_now_a - at_t
  if hp_now_a <= 0:
    print("Yes")
    break
  hp_now_t = hp_now_t - at_a
  if hp_now_t<= 0:
    print("No")
    break

Measured memory_bytes: 61676
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll INF = 1e18;

int main() {
	ios::sync_with_stdio(0), cin.tie(0);

	int n;
	cin >> n;
	int first;
	cin >> first;
	array<ll, 3> dp = {first, -INF, -INF};
	for (int i = 0; i < n-1; i++) {
		array<ll, 3> ndp = {-INF, -INF, -INF};
		char op;
		cin >> op;
		int num;
		cin >> num;
		if (op == '-') num = -num;
		for (int a = 0; a < 3; a++, num = -num) {
			if (dp[a] == -INF) continue;
			for (int b = a-1; b <= a+1; b++) {
				if (!(0 <= b && b < 3)) continue;
				if (op == '+' && b > a) continue;
				ndp[b] = max(ndp[b], dp[a] + num);
			}
		}
		swap(dp, ndp);
	}
	cout << *max_element(dp.begin(), dp.end()) << '\n';

	return 0;
}


Measured memory_bytes: 384
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols
    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])
    return ret


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_map_as_int(H):
    '''
    #→1,.→0として読み込む
    '''
    ret = []
    for _ in range(H):
        ret.append([1 if s == '#' else 0 for s in read()[:-1]])
        # 内包表記はpypyでは若干遅いことに注意
        # #numpy使うだろうからこれを残しておくけど
    return ret


MOD = 10**9 + 7
# default import
from itertools import product, permutations, combinations
H, W = read_ints()
S = read_map_as_int(H)  # が1 .が0

dp = [[100000] * (W) for _ in range(H)]  # -1アクセス用に余分に取っておく
# 初期化
dp[0][0] = S[0][0]

for i, j in product(range(H), range(W)):
    if i == 0 and j == 0:
        continue
    if i != 0:
        dp[i][j] = min(dp[i][j], dp[i - 1][j]
                       + (1 if S[i][j] == 1 and S[i - 1][j] == 0 else 0))
    if j != 0:
        dp[i][j] = min(dp[i][j], dp[i][j - 1]
                       + (1 if S[i][j] == 1 and S[i][j - 1] == 0 else 0))

print(dp[-1][-1])


Measured memory_bytes: 42736
#include<stdio.h>
int main(void){
	int c[3][4]={0},i,j;
	for(i=1;i<4;i++){
		for(j=1;j<4;j++){
			scanf("%d",&c[i][j]);
		}
	}
	for(i=1;i<3;i++){
		for(j=i;j<4;j++){
			if(c[i][i]+c[j][j]-c[i][j]-c[j][i]){
				printf("No");
				return 0;
			}
		}
	}
	printf("Yes");
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int INF = 1e9;
const ll INFF = 1e18;
const int MAXN = 510;
const int MOD = 1e9 + 7;


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int a,b,c;
	cin >> a >> b >> c;
	if (a > b)
		swap(a,b);
	if ((a <= c) && (c <= b))
		cout << "Yes\n";
	else
		cout << "No\n";	
}

Measured memory_bytes: 892
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n; cin >> n;
    int cntac=0,cntwa=0,cnttle=0,cntre=0;
    for(int ix=0;ix<n;ix++){
        string  s; cin >> s;
        if(s == "AC") cntac++;
        if(s == "WA") cntwa++;
        if(s == "TLE") cnttle++;
        if(s == "RE") cntre++;
    }
    cout << "AC x " << cntac << endl;
    cout << "WA x " << cntwa << endl;
    cout << "TLE x " << cnttle << endl;
    cout << "RE x " << cntre << endl;
}

Measured memory_bytes: 3528
n,m,x,y = map(int,input().split())
a_city=list(map(int,input().split()))
b_city=list(map(int,input().split()))
a=max(a_city)
b=min(b_city)
c = max(x,a)
d = min(y,b)
if c<d:
  print("No War")
else:
  print("War")

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define inf INT_MAX
#define INF LLONG_MAX
#define ll long long
#define ull unsigned long long
#define M (int)(1e9+7)
#define P pair<int,int>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define int ll
#define vi vector<int>
#define IP pair<int,P>
#define PI pair<P,int>
#define PP pair<P,P>
#define Yes(f){cout<<(f?"Yes":"No")<<endl;}
#define YES(f){cout<<(f?"YES":"NO")<<endl;}
#define MPlus(x,y) {x=(x+y)%M;}
#define MSub(x,y) {x=(x-y+M)%M;}
#define MMul(x,y) {x=(x*y)%M;}

int n;
int a[10];
int ans=0;

void f(int b[],int k){
  if(k==n){
    int aa[n]; 
    rep(i,n){
      aa[i]=a[i]+b[i];
    }
    int s=1;
    rep(i,n){
      s*=aa[i];
    }
    ans+=(s%2==0);
    return;
  }

  for(int i=-1;i<2;i++){
    b[k]=i;
    f(b,k+1);
  }
}

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(20);

  cin>>n;
  rep(i,n){
    cin>>a[i];
  }

  int b[n];

  f(b,0);

  cout<<ans<<endl;

}

Measured memory_bytes: 256
h, w = [int(x) for x in input().split()]
p = []
for _ in range(h):
    p.append(list(input()))
print("#" * (w + 2))
for l in p:
    l[0:0] = "#"
    l[len(l):] = "#"
    print("".join(l))
print("#" * (w + 2))

Measured memory_bytes: 3060
def main():
    N = int(input())
    A = list(map(int, input().split()))
    AA = [(v, i) for i, v in enumerate(A)]
    AA.sort(reverse=True)
    dp = [[0] * (N+1) for _ in range(N+1)]
    for i, (a, b) in enumerate(AA, start=1):
        for x in range(i+1):
            y = i - x
            if y == 0:
                dp[x][y] = dp[x-1][y] + abs(b - x+1) * a
            elif x == 0:
                dp[x][y] = dp[x][y-1] + abs(N-y-b) * a
            else:
                dp[x][y] = max(dp[x-1][y] + abs(b - x + 1) * a, dp[x][y-1] + abs(N-y-b) * a)
    r = 0
    for i in range(N+1):
        r = max(r, dp[i][N-i])
    return r
print(main())


Measured memory_bytes: 136092
#include<stdio.h>
#include<stdlib.h>

typedef struct node{
  struct node *parent;
  int key;
  struct node *left;
  struct node *right;
}Node;

Node *head;
void insert(Node *,int);
Node *make_node(Node *,int,Node *,Node *);
void inorder_print(Node *);
void preorder_print(Node *);
void free_node(Node *);
int find(Node *,int);

int main(){
  int n,key;
  char command[7];
  head = make_node(NULL,key,NULL,NULL);
  scanf("%d",&n);
  while(n--){
    scanf("%s",command);
    if(command[0] == 'i'){
     
      scanf("%d",&key);
      insert(head->left,key);
    }
    else if(command[0] == 'f'){
      scanf("%d",&key);
      if(find(head->left,key))printf("yes\n");
      else printf("no\n");
    } 
    else{
      inorder_print(head->left);
      printf("\n");
      preorder_print(head->left);
      printf("\n");
    }
  }
  free_node(head->left);
  free(head);
}

void insert(Node *node,int in_key){
  if(node == NULL)head->left = make_node(node,in_key,NULL,NULL);
  else{
    if(node->key > in_key){
      if(node->left == NULL) node->left = make_node(node,in_key,NULL,NULL);
      else insert(node->left,in_key);
    }
    else{
      if(node->right == NULL) node->right = make_node(node,in_key,NULL,NULL);
      else insert(node->right,in_key);
    }
  }
}

Node *make_node(Node *p,int k,Node *l,Node *r){
  Node *new;

  new = malloc(sizeof(Node));
  if(new == NULL){
    free(new);
    printf("node Generation failed\n");
    exit(1);
  }
  new->parent = p;
  new->key = k;
  new->left = l; 
  new->right= r;
  return new;
}
void inorder_print(Node *next){
  if(next != NULL){
    inorder_print(next->left);
    printf(" %d",next->key);
    inorder_print(next->right);
  }
}
void preorder_print(Node *next){
  if(next != NULL){
    printf(" %d",next->key);
    preorder_print(next->left);
    preorder_print(next->right);
  }
}

int find(Node *n,int k){
  if(n->key == k)return 1;
  else if(n->key > k){
    if(n->left != NULL)return find(n->left,k);
    else return 0;
  }
  else if(n->key < k){
    if(n->right != NULL)return find(n->right,k);
    else return 0;
  }
  else return 0;
}
void free_node(Node *n){
  if(n->left != NULL){
    free_node(n->left);
    free(n->left);
  }
  if(n->right != NULL){
    free_node(n->right);
    free(n->right);
  }
}


Measured memory_bytes: 20556
#include <iostream>
#include <string>
#include <algorithm>
#include <cassert>
#include <limits>
#include <numeric>
#include <type_traits>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <functional>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

typedef long long ll;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n)  FOR(i,0,n)

int main(){
	ll N, X;
	cin >> N >> X;
	ll L[N];
	REP(i, N){
		cin >> L[i];
	}
	ll D = 0;
	int ans = 0;
	REP(j, N + 1){
			if(D <= X){
			D = D + L[j];
			ans++;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<algorithm>
using namespace std;
int use[110000];
int main(){
	int a;scanf("%d",&a);
	int now=0;
	for(int i=1;;i++){
		use[i]=1;
		now+=i;
		if(now>=a){
			use[now-a]=0;
			break;
		}
	}
	for(int i=1;i<110000;i++){
		if(use[i])printf("%d\n",i);
	}
}

Measured memory_bytes: 256
n,x = map(int,input().split())
import fractions
x_list = list(map(int, input().split()))
a = []
for i in range(n):
    a.append(abs(x_list[i] - x))
ans = a[0]
for i in range(1, len(a)):
    ans = fractions.gcd(ans, a[i])
print(ans)

Measured memory_bytes: 16296
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

int n,w;
ll dp[125252];

int main(){
  scanf("%d%d",&n,&w);
  fill(dp,dp+w+1,-1ll<<60);
  dp[0] = 0;
  REP(i,n){
    int a,b;
    scanf("%d%d",&a,&b);
    FORR(j,0,w+1-a)CHMAX(dp[j+a],dp[j]+b);
  }
  printf("%lld\n",*max_element(dp,dp+w+1));
  return 0;
}


Measured memory_bytes: 1024
use std::str::FromStr;
use std::io::*;

fn main() {
    let i = stdin();
    let mut o = Vec::new();
    run(&mut i.lock(), &mut o);
    stdout().write_all(&o).unwrap();
}

fn run<R: BufRead, W: Write>(i: &mut R, o: &mut W) {
    let buf = &mut String::new();
    let w: usize;
    let h: usize;
    let d: usize;
    {
        let i = &mut next_line(i, buf).split(' ');
        h = next(i);
        w = next(i);
        d = next(i);
    }
    let wh = w * h;
    let mut a_to_xy = vec![(0, 0); wh + 1];

    for y in 0..h {
        let i = &mut next_line(i, buf).split(' ');
        for x in 0..w {
            let a: usize = next(i);
            a_to_xy[a] = (x, y);
        }
    }
    fn abs_sub(x0: usize, s1: usize) -> usize {
        (x0 as isize - s1 as isize).abs() as usize
    }

    let mut mps = vec![0; wh + 1];
    for i in 1..wh + 1 - d {
        let xy0 = a_to_xy[i];
        let xy1 = a_to_xy[i + d];
        mps[i + d] = mps[i] + abs_sub(xy0.0, xy1.0) + abs_sub(xy0.1, xy1.1);
    }
    std::mem::drop(a_to_xy);

    let q: usize;
    {
        let i = &mut next_line(i, buf).split(' ');
        q = next(i);
    }
    for _ in 0..q {
        let i = &mut next_line(i, buf).split(' ');
        let l: usize = next(i);
        let r: usize = next(i);
        let mp = mps[r] - mps[l];
        writeln!(o, "{}", mp).unwrap();
    }
}

fn next_line<'a, 'b, R: BufRead>(i: &'a mut R, s: &'b mut String) -> &'b str {
    s.clear();
    i.read_line(s).unwrap();
    s.trim()
}
fn next<'a, T: FromStr, I: std::iter::Iterator<Item = &'a str>>(i: &mut I) -> T {
    i.next().unwrap().parse().ok().unwrap()
}


Measured memory_bytes: 6524
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;

#ifdef DEBUG
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#else
#define eprintf(...) ;
#endif

#define sz(x) ((int) (x).size())
#define TASK "text"

const int inf = (int) 1.01e9;
const long long infll = (long long) 1.01e18;
const ld eps = 1e-9;
const ld pi = acos((ld) -1);

mt19937 mrand(random_device{} ()); 

int rnd(int x) {
  return mrand() % x;
}

void precalc() {
}

long long gcd(long long a, long long b) {
  return (b ? gcd(b, a % b) : a);
}

long long lcm(long long a, long long b) {
  return a / gcd(a, b) * b;
}

const int maxn = 505;
int n;

int read() {
  if (scanf("%d", &n) < 1) {
    return false;
  }
  return true;
}

const long long maxx = (long long) 1e15 + 1;
const int gox[] = {1, 0, -1, 0};
const int goy[] = {0, 1, 0, -1};
long long a[maxn][maxn];

void solve() {
  vector<int> prs;
  for (int x = 2; sz(prs) < 1500; x++) {
    bool ok = true;
    for (int d = 2; d * d <= x; d++) {
      if (!(x % d)) {
        ok = false;
        break;
      }
    }
    if (ok) {
      prs.push_back(x);
    }
  }
  set<long long> used;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (!((i + j) & 1)) {
        long long x = (long long) prs[maxn / 2 + i / 2] * prs[1 + j / 2];
        if (used.count(x)) {
          x *= 2;
        }
        assert(x < maxx);
        assert(!used.count(x));
        a[i][j] = x;
        used.insert(x);
      }
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (!((i + j) & 1)) {
        continue;
      }
      long long x = 1;
      for (int dir = 0; dir < 4; dir++) {
        int ni = i + gox[dir], nj = j + goy[dir];
        if (ni < 0 || ni >= n || nj < 0 || nj >= n) {
          continue;
        }
        x = lcm(x, a[ni][nj]);
      }
      long long y = x;
      while (used.count(x + 1)) {
        x += y;
      }
      x++;
      eprintf("%d %d\n", i, j);
      assert(x < maxx);
      a[i][j] = x;
      used.insert(x);
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      printf("%lld ", a[i][j]);
    }
    printf("\n");
  } 
}

int main() {
  precalc();
#ifdef DEBUG
  assert(freopen(TASK ".in", "r", stdin));
  assert(freopen(TASK ".out", "w", stdout));
#endif
  while (read()) {
    solve();
#ifdef DEBUG
    eprintf("Time %.2f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
  }
  return 0;
}


Measured memory_bytes: 16640