akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
int n,m,A[5010],B[5010][210];
ll matrix[5010][5010];int l[5010],r[5010];
int st[5010],tp;
ll sum[5010];
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=2;i<=n;i++) {scanf("%d",&A[i]);sum[i]=sum[i-1]+A[i];}
    for (int i=1;i<=n;i++) 
        for (int j=1;j<=m;j++)
            scanf("%d",&B[i][j]);
    for (int j=1;j<=m;j++)
    {
        tp=0;
        for (int i=1;i<=n;i++)
        {
            while (tp&&B[i][j]>B[st[tp]][j]) r[st[tp--]]=i-1;
            st[++tp]=i;
        }
        while (tp) r[st[tp--]]=n;
        tp=0;
        for (int i=n;i;i--)
        {
            while(tp&&B[i][j]>=B[st[tp]][j]) l[st[tp--]]=i+1;
            st[++tp]=i;
        }
        while (tp) l[st[tp--]]=1;
        for (int i=1;i<=n;i++)
        {
            matrix[i+1][r[i]+1]+=B[i][j];
            matrix[l[i]][i]+=B[i][j];
            matrix[l[i]][r[i]+1]-=B[i][j];
            matrix[i+1][i]-=B[i][j];
        }
    }
    ll ans=0;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
        {
            matrix[i][j]+=matrix[i-1][j]+matrix[i][j-1]-matrix[i-1][j-1];
            if (i<=j) ans=max(ans,matrix[i][j]-(sum[j]-sum[i]));
        }
    cout<<ans;
}

Measured memory_bytes: 200448
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
  ll i, a, b, k, atmp = 0, btmp = 0;
  cin >> a >> b >> k;
  if (k % 2 == 0) {
    for (i = 0; i < k / 2; ++i) {
      if (a % 2 == 0) {
        a /= 2;
        b += a;
      } else {
        a -= 1;
        a /= 2;
        b += a;
      }
      if (b % 2 == 0) {
        b /= 2;
        a += b;
      } else {
        b -= 1;
        b /= 2;
        a += b;
      }
    }
  } else {
    for (i = 0; i < k / 2; ++i) {
      if (a % 2 == 0) {
        a /= 2;
        b += a;
      } else {
        a -= 1;
        a /= 2;
        b += a;
      }
      if (b % 2 == 0) {
        b /= 2;
        a += b;
      } else {
        b -= 1;
        b /= 2;
        a += b;
      }
    }
    if (a % 2 == 0) {
      a /= 2;
      b += a;
    } else {
      a -= 1;
      a /= 2;
      b += a;
    }
  }
  cout << a << ' ' << b << "\n";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=1e9+7;
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

ll dp[100001][13]={0};
int main(){
    string S; cin>>S;
    int N=S.length();

    dp[0][0]=1;

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < 13; ++j) {
            if(S[N-1-i]=='?'){
                for(int k=0;k<=9;++k){
                    ll add=modpow(10,i,13);
                    (dp[i+1][(k*add+j)%13]+=dp[i][j])%=MOD;
                }
            }else{
                int num=S[N-1-i]-'0';
                ll add=modpow(10,i,13);
                (dp[i+1][(num*add+j)%13]+=dp[i][j])%=MOD;
            }
        }
    }

    cout<<dp[N][5]<<endl;

    return 0;
}



Measured memory_bytes: 10624
#include <stdio.h>
long long rui[100005],ret=0LL; int n,m,cur=1,x;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=2;i<=n;i++) { scanf("%d",&x); rui[i]=rui[i-1]+1LL*x;}
	for(int i=1;i<=m;i++){
		scanf("%d",&x);
		if(x>0){ ret+=rui[x+cur]-rui[cur]; cur+=x;}
		else{ ret+=rui[cur]-rui[cur+x]; cur+=x;}
	}
	printf("%lld\n",ret%100000);
}

Measured memory_bytes: 1804
#include <bits/stdc++.h>
#include <set>
#define rep(i,n) for (int i=0; i < (n); ++i)
#define all(a) a.begin(), a.end()
using ll = long long;
using namespace std;

int main() {
  int x; cin >> x;
  int devide = x / 500;
  int remain = x % 500;
  int sum_500 =0;
  int sum_5 = 0;
  
  sum_500 = devide*1000;
  sum_5 = remain/5 * 5;
  cout << sum_5 +sum_500 << endl;
  return 0;
  
  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define rng(a) a.begin(), a.end()
#define ina(n,a) cin >> n; for(int i = 1; i <= n; i++) cin >> a[i]
#define sz(x) (int)(x).size()
#define se second
#define fi first
#define prev            coyhhhhhhyoc    
#define next          sdNNNmNNNNNNNmds  
#define y0           hNNNNy_yNNNNNN_sNh
#define y1          mNNNNNdtdNNNNNNtsNNm
#define yn          mNNNNNNNNy___smNNNms
#define tm            oooooosyysooooot 
#define read               tyhyt        
#define rank              ytmNmo         
#define index              yyy
#define pb push_back
#define pcnt __builtin_popcountll
#define rrep(i,a,b) for(int i = (b); i >= (a); i--)
#define rall(x,a) for(auto x : a)
#define MOD 1000000007
#define endl "\n"
typedef long long ll;
using namespace std;

const int N = 1111111;
int a[N], cnt[N], cntd[N];
int n;

int solve() {
    ina(n, a);
    rep(i, 1, n) {
        cnt[a[i]]++;
    }
    bool ok = true;
    rep(x, 2, N - 1) {
        int cur = 0;
        for(int y = x; y < N; y += x) {
            cur += cnt[y];
        }
        if(cur > 1) {
            ok = false;
            break;
        }
    }
    if(ok) {
        cout << "pairwise coprime" << endl;
        return 0;
    }
    int g = a[1];
    rep(i, 2, n) {
        g = __gcd(g, a[i]);
    }
    if(g == 1) {
        cout << "setwise coprime" << endl;
        return 0;
    }
    cout << "not coprime" << endl;
    return 0;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    while(t--) {
        solve();
    }
    return 0;
}


Measured memory_bytes: 11296
#include<bits/stdc++.h>
#define ALL(c) (c).begin(),(c).end()
#define EACH(i,c) for(auto i=(c).begin();i!=(c).end();++i)
typedef long long ll;
using namespace std;

int main(){
	int N;
	cin >> N;
	ll mx = N;
	for(ll i = 1; i <= N; ++i){
		if(N - i <= (i-1) * i / 2){
			mx = min(mx, i);
		}
	}
	ll sum = 0;
	vector<int> ans;
	for(int i = mx; sum <= N && i >= 1; --i){
		if(N - sum >= i){
			sum += i;
			ans.push_back(i);
		}
	}
	sort(ALL(ans));
	for(int i: ans){
		cout << i << endl;
	}
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
int N;  
string str;
int main(){
  cin >> str;
  cin >> N;
  int i;
  for(i=0;i<str.size();i++){
    //cout << str <<endl<< i <<endl;;
    if(123-str[i]<=N&&str[i]!='a'){
      N-=123-str[i];
      str[i]='a';
    }
  }
  str[i-1]+=N%26;
  cout <<str<<endl;
  return 0;
}

Measured memory_bytes: 512
/// Rustで競技プログラミングの入力をスッキリ記述するマクロ
///
/// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[inline]
#[allow(dead_code)]
fn gcd(mut m: u64, mut n: u64) -> u64 {
    if m < n {
        std::mem::swap(&mut m, &mut n);
    }

    loop {
        let k = m % n;
        if k == 0 {
            return n;
        }

        m = n;
        n = k;
    }
}

#[inline]
#[allow(dead_code)]
fn lcm(m: u64, n: u64) -> u64 {
    m / gcd(m, n) * n
}

macro_rules! eprint(
    ($($arg:tt)*) => { {
        use std::io::Write;
        let r = write!(&mut ::std::io::stderr(), $($arg)*);
        r.expect("failed printing to stderr");
    } }
);

macro_rules! eprintln(
    ($($arg:tt)*) => { {
        use std::io::Write;
        let r = writeln!(&mut ::std::io::stderr(), $($arg)*);
        r.expect("failed printing to stderr");
    } }
);

macro_rules! dbg {
    ($val:expr) => {
        // Use of `match` here is intentional because it affects the lifetimes
        // of temporaries - https://stackoverflow.com/a/48732525/1063961
        match $val {
            tmp => {
                eprintln!(
                    "[{}:{}] {} = {:#?}",
                    file!(),
                    line!(),
                    stringify!($val),
                    &tmp
                );
                tmp
            }
        }
    };
}

fn main() {
    input! {
        n: usize,
        a_v: [u64; 3 * n],
    }

    let mut a_v = a_v;
    a_v.sort_by(|a, b| b.cmp(a));

    let answer = a_v
        .chunks(2)
        .take(n)
        .map(|ab| ab[1])
        .fold(0, |acc, x| acc + x);
    println!("{}", answer);
}


Measured memory_bytes: 8444
#include <iostream>
#include <string>

using namespace std;

int main() {
	int n; cin >> n;
	string s; cin >> s;
	int north = 0, east = 0;
	for (int i = 0; i < n; ++i) {
		if (s[i] <= 'M') north++;
		else if (s[i] <= 'Z') north--;
		else if (s[i] <= 'm') east++;
		else  east--;
	}
	string ans;
	while (north != 0 || east != 0) {
		if (north > 0) ans += 'A', north--;
		else if (north < 0) ans += 'N', north++;
		if (east > 0) ans += 'a', east--;
		else if (east < 0) ans += 'n', east++;
	}
	cout << ans.size() << endl << ans << endl;

	return 0;
}


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

using namespace std;
using ll = long long;

int main(void) {
  double d, s, t;
  cin >> d >> s >> t;
  if (d / s <= t) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}

Measured memory_bytes: 3692
def solve():
    S=input()
    n=len(S)
    S1=[1]
    k=1
    for i in range(1,n):
        if S[i] not in S[:i]:
            k+=1
            S1.append(k)
        else:
            num=S1[S.find(S[i])]
            S1.append(num)
    return S1

S1=solve()
T1=solve()

if S1==T1:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 12564
def generator(n):
    if n == 1:
        for i in range(1, 10):
            yield i
    else:
        for a in generator(n - 1):
            for i in range(10):
                if abs(i - (a % 10)) <= 1:
                    yield 10 * a + i


k = int(input())
A = []
for i in range(1, 11):
    for a in generator(i):
        A.append(a)
print(A[k - 1])


Measured memory_bytes: 12056
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+9;
int main()
{
	ll i,j,k,n,sum[maxn][3]={0},ans=0;
	char s[maxn];
	scanf("%d%s",&n,s+1);
	for(i=n;i>=1;i--)
	{
		sum[i][0]=sum[i+1][0];sum[i][1]=sum[i+1][1];sum[i][2]=sum[i+1][2];
		if(s[i]=='R')sum[i][0]++;
		if(s[i]=='G')sum[i][1]++;
		if(s[i]=='B')sum[i][2]++;
	}
	for(i=1;i<=n;i++)
	{
		for(j=i+1;j<=n;j++)
		{
			if(s[i]==s[j])continue;
			if(s[i]!='R'&&s[j]!='R')
			{
				ans=ans+sum[j+1][0];
				if(s[j+(j-i)]=='R')ans--;
			}
			if(s[i]!='G'&&s[j]!='G')
			{
				ans=ans+sum[j+1][1];
				if(s[j+(j-i)]=='G')ans--;
			}
			if(s[i]!='B'&&s[j]!='B')
			{
				ans=ans+sum[j+1][2];
				if(s[j+(j-i)]=='B')ans--;
			}
		}
	}
	printf("%lld\n",ans);
}

Measured memory_bytes: 6180
#include<iostream>
using namespace std;
int main(){
  int n,h=0,h1=0,h2=0;
  cin >> n;
  int ans[n],p[n],p1[n],p2[n];
  for(int i=0;i<n;i++) ans[i] = 0;
  for(int i=0;i<n;i++){
    for(int j=0;j<3;j++){
      if(j==0) cin >> p[i];
      else if(j==1) cin >> p1[i];
      else cin >> p2[i];
    }
  }
  for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
      if(p[i]==p[j]){
	p[j] = 0;
	h = 1;
      }if(p1[i]==p1[j]){
	p1[j] = 0;
	h1 = 1;
      }if(p2[i]==p2[j]){
	p2[j] = 0;
	h2 = 1;
      }
    }if(h==1){
	p[i] = 0;
	h = 0;
      }if(h1==1){
	p1[i] = 0;
	h1 = 0;
      }if(h2==1){
	p2[i] = 0;
	h2 = 0;
      }
    }
  for(int i=0;i<n;i++) ans[i] = p[i] + p1[i] + p2[i];
  for(int i=0;i<n;i++) cout << ans[i] << endl;
  return 0;
}

Measured memory_bytes: 1160
n, m, l = [int(i) for i in input().split()]

A = []
B = []
C = []

for ni in range(n):
    A.append([int(i) for i in input().split()])

for mi in range(m):
    B.append([int(i) for i in input().split()])

for i in range(n):
    C.append([])
    for j in range(l):
        C[i].append(0)
        for k in range(m):
            C[i][j] += A[i][k] * B[k][j]

for ni in range(n):
    print(" ".join([str(s) for s in C[ni]]))

Measured memory_bytes: 8980
#include<stdio.h>

int n, A[50];

int solve(int x, int m) {
	if (m == 0) return 1;
	if (x >= n) return 0;
	int res = solve(x + 1, m) || solve(x + 1, m - A[x]);
	return res;
}

int main()
{
	int q, M, i;
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%d", &A[i]);
	}
	scanf("%d", &q);
	for (i = 0; i < q; i++) {
		scanf("%d", &M);
		if (solve(0, M)) {
			printf("yes\n");
		}
		else {
			printf("no\n");
		}
	}
    return 0;
}

Measured memory_bytes: 2604
#include<cstdio>
#include<algorithm>
#include<functional>
const int P=1000000007;
int a[107],f[107][107][507];
int read(){int x;scanf("%d",&x);return x;}
void inc(int&a,int b){a+=b-P,a+=a>>31&P;}
int mul(int a,int b){return 1ll*a*b%P;}
int main()
{
    int n=read(),m=read(),ans=0;
    for(int i=1;i<=n;++i) a[i]=read();
    std::sort(a+1,a+n+1,[](int i,int j){return i>j;}),f[1][1][a[1]]=1;
    for(int i=2;i<=n;++i)
	for(int j=0;j<=i;++j)
	    for(int k=0;k<=m;++k)
		if(f[i-1][j][k])
		{
		    inc(f[i][j][k],mul(k-(a[i]-1)*j,f[i-1][j][k]));
		    if(k+a[i]<=m) inc(f[i][j+1][k+a[i]],mul(j+1,f[i-1][j][k]));
		    for(int l=1;l<a[i]&&k+l<=m;++l) inc(f[i][j][k+l],mul(j*2,f[i-1][j][k]));
		    if(j>1) for(int l=0;l<a[i]&&k+l<=m;++l) inc(f[i][j-1][k+l],mul((j-1)*(a[i]-l-1),f[i-1][j][k]));
		}
    for(int i=1;i<=n;++i) inc(ans,f[n][i][m]);
    printf("%d",ans);
}


Measured memory_bytes: 20992
//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please

const int cm = 1 << 17;
char cn[cm], * ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}

const int dm = 1 << 22;
char dn[dm], * di = dn;
char C[10];
int keta = 0;
inline void putint(int X) {
	keta = 0;
	while (X) {
		*(C + keta) = '0' + X % 10;
		X /= 10;
		keta++;
	}
	for (int i = keta - 1; i >= 0; i--)* di++ = (*(C + i));
	*di++ = '\n';
}
inline void putmae() {
	for (int i = keta - 1; i >= 0; i--)* di++ = (*(C + i));
	*di++ = '\n';
}

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


	int N = getint();
	int n = 1 << N;
	int dp1[1 << 18], dp2[1 << 18];
	rep(i, n) {
		dp1[i] = getint();
		dp2[i] = 0;
	}

	rep(k, N) {
		int m = 1 << k;
		int m2 = ~(1 << k);
		for (int j = n - 1 & m2; j >= 0; j = j - 1 & m2) {
			int i = j | m;
			int k = min(dp1[i], dp1[j]);
			dp1[i] += dp1[j] - k;
			dp2[i] = max(dp2[i], k);
			dp2[i] = max(dp2[i], dp2[j]);
		}
	}

	int saidai = 0;
	rep1(i, n - 1) {
		if (saidai < dp1[i] + dp2[i]) {
			saidai = dp1[i] + dp2[i];
			putint(saidai);
		}
		else putmae();
	}
	fwrite(dn, 1, di - dn, stdout);

	Would you please return 0;
}

Measured memory_bytes: 9216
#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <unordered_map>

#define REP(i, n) for (int i = 0; i < n; i++)
#define ll long long int

using namespace std;

int main()
{
  int x;
  cin >> x;
  if (x == 3 || x == 5 || x == 7)
  {
    cout << "YES" << endl;
  }
  else
  {
    cout << "NO" << endl;
  }
}


Measured memory_bytes: 256
//It is mainly modular Exponentiation
#include<bits/stdc++.h>
using namespace std;
#define INF 1<<30
#define maxn 100005
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0) ,cout.tie(0);
typedef long long ll;
using u64 = uint64_t;
using u128 =__uint128_t;
u64 binpower(u64 base,u64 e,u64 mod)
{
    u64 result=1;
    base%=mod;
    while(e)
    {
        if(e&1)
        result = (u128)result*base%mod;

        base=(u128)base*base%mod;

        e>>=1;
    }
    return result;
}
int main()
{
    long long int t,x,i,j,n,b,m;
    m=1e9+7;
    cin>>n;
    x=((binpower(10,n,m)%m)+(binpower(8,n,m)%m))%m;
    b=((binpower(9,n,m)%m)*(2%m))%m;
    cout<<((x%m)-(b%m)+m)%m<<endl;
   return 0;
}


Measured memory_bytes: 3632
#include <vector>
#include <iostream>
#include <utility>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
#include <tuple>
#include <queue>
#include <functional>
#include <cmath>
#include <iomanip>
#include <map>
#include <set>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <complex>
#include <iterator>
#include <array>
#include <memory>
#include <stack>
#define vi vector<int>
#define vvi vector<vector<int> >
#define ll long long int
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
#define ld long double
#define INF 1e9
#define EPS 0.0000000001
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define all(in) in.begin(), in.end()
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
#define MAX 9999999
using namespace std;
typedef pair<int, int> pii;
typedef pair<double,double>pdd;
typedef pair<ll,ll>pll;
string key;
ll ans=0;
void cal(string temp){
    string sakiyama;
    for(int i=0; i<temp.size();i++){
        if(temp[i]=='+'){
            ans+=stoi(sakiyama);
            sakiyama.clear();
        }else sakiyama.push_back(temp[i]);
    }
    ans+=stoll(sakiyama);
}
void dfs(string s,int range){
    int cnt=range;
    if(range==(int)key.size()){cal(s); return;}
    string temp=s;
    for(int i=0; i<temp.size();i++){
        if(s[i]=='+')continue;
        else{
            if(!cnt){
                temp.insert(temp.begin()+i,'+');
                dfs(temp,range+1);
                dfs(s,range+1);;
            }
            cnt--;
        }
    }
}
int main(){
    cin>>key;
    dfs(key,1);
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<vector>
#include<cmath>
#include<queue>
#include<string.h>
#include<map>
#include<set>
#include<algorithm>
#define ll long long
#define pi pair < ll,ll >
#define mp(a,b) make_pair(a,b)
#define rep(i,a,b) for(int i = a;i < b;i++)
#define N 404
#define INF 1e15

using namespace std;

ll n,ar[N];
ll dp[N][N];
ll pre[N];

ll get_sum(ll i,ll j)
{
    if(i==0)
        return pre[j];
    return pre[j]-pre[i-1];
}

ll solve(ll i,ll j)
{
    if(i >= j)
        return 0;
    if(dp[i][j])
        return dp[i][j];

    ll res = INF;
    ll suma = get_sum(i,j);

    rep(k,i,j)
    {
        res = min(res,solve(i,k)+solve(k+1,j)+suma);
    }

    return dp[i][j] = res;
}

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

    cin >> n;

    rep(i,0,n)
    {
        cin >> ar[i];

        if(i == 0)
            pre[i] = ar[i];
        else
            pre[i] = pre[i-1]+ar[i];
    }

    cout << solve(0,n-1);

    return 0;
}



Measured memory_bytes: 1536
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func max(nums ...int) int {
	ret := nums[0]
	for _, v := range nums {
		if v > ret {
			ret = v
		}
	}
	return ret
}

func min(nums ...int) int {
	ret := nums[0]
	for _, v := range nums {
		if v < ret {
			ret = v
		}
	}
	return ret
}

func main() {
	sc.Split(bufio.ScanWords)
	n := nextInt()
	col := make([]int, 9)
	for i := 0; i < n; i++ {
		r := nextInt() / 400
		if r >= 9 {
			r = 8
		}
		col[r]++
	}

	maxAns := 0
	for i := 0; i < 8; i++ {
		if col[i] > 0 {
			maxAns++
		}
	}
	maxAns = maxAns + col[8]

	minAns := 0
	for i := 0; i < 8; i++ {
		if col[i] > 0 {
			minAns++
		}
	}
	if minAns == 0 {
		minAns = 1
	}

	puts(minAns, maxAns)

	wt.Flush()
}

var (
	sc = bufio.NewScanner(os.Stdin)
	wt = bufio.NewWriter(os.Stdout)
)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	i, _ := strconv.Atoi(next())
	return i
}

func puts(a ...interface{}) {
	fmt.Fprintln(wt, a...)
}


Measured memory_bytes: 640
package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

func main() {
    sc.Split(bufio.ScanWords)
	n := nextInt()
	var a,b,c []int
	a = make([]int, n + 1)
	b = make([]int, n + 1)
	c = make([]int, n + 1)
	
    for i := 1; i <= n; i++ {
        a[i] = nextInt()
    }
    for i := 1; i <= n; i++ {
        b[i] = nextInt()
    }
    for i := 1; i <= n - 1; i++ {
        c[i] = nextInt()
    }

	score := 0

	for i := 1; i <= n; i++ {
		score += b[a[i]]
		//fmt.Println(b[a[i]])
		if i > 0 && a[i] == (a[i-1] + 1) {
			score += c[a[i-1]]
			//fmt.Println(c[a[i]])
		}
	}

    fmt.Println(score)
}

Measured memory_bytes: 640
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cerr<<*i<<" "; cerr<<endl; }
inline bool valid(int x, int y, int W, int H){ return (x >= 0 && y >= 0 && x < W && y < H); }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
typedef vector<int> Node;
struct S{
  S() : N(0), M(0) {}
  int N, M;
  vector<char> cv;
  vector<Node> G;
};
S input(){
  S s;
  cin >> s.N >> s.M;
  s.cv = vector<char>(s.N);
  REP(i, s.N) cin >> s.cv[i];
  s.G = vector<Node>(s.N);
  REP(i, s.M){
    int a, b; cin >> a >> b;
    s.G[a - 1].push_back(b - 1);
  }
  return s;
}
set<char> infinite(S& s){
  set<char> res;
  bool d[100][100] = {};
  REP(i, s.N)FORIT(e, s.G[i]){
    d[i][*e] = true;
  }
  REP(k, s.N)REP(i, s.N)REP(j, s.N) d[i][j] |= (d[i][k] & d[k][j]);
  REP(i, s.N) if(d[i][i]) res.insert(s.cv[i]);
  return res;
}
int memo[100][100];
int dfs(int u, int v, S& A, S& B){
  if(memo[u][v] != -1) return memo[u][v];
  int& res = memo[u][v];
  res = 0;
  if(A.cv[u] == B.cv[v]){
    FORIT(e1, A.G[u])FORIT(e2, B.G[v]){
      res = max(res, dfs(*e1, *e2, A, B));
    }
    res += 1;
  }else{
    FORIT(e1, A.G[u]){
      res = max(res, dfs(*e1, v, A, B));
    }
    FORIT(e2, B.G[v]){
      res = max(res, dfs(u, *e2, A, B));
    }
    FORIT(e1, A.G[u])FORIT(e2, B.G[v]){
      res = max(res, dfs(*e1, *e2, A, B));
    }
  }
  return res;
}
int solve(S& A, S& B){
  set<char> inf1 = infinite(A);
  set<char> inf2 = infinite(B);
  FORIT(it, inf1)if(inf2.count(*it)) return -1;
  memset(memo, -1, sizeof(memo));
  int ans = 0;
  REP(i, A.N)REP(j, B.N) ans = max(ans, dfs(i, j, A, B));
  return ans;
}
int main(){
    S A = input();
    S B = input();
    cout << solve(A, B) << endl;
  return 0;
}

Measured memory_bytes: 1556
s = gets.chomp.chars
first = s[0]
last = s[-1]
cnt = 0
while !s.empty?
  if first == last
    s.shift
    s.pop
    first = s[0]
    last = s[-1]
  elsif first == "x"
    s.shift
    first = s[0]
    cnt += 1
  elsif last == "x"
    s.pop
    last = s[-1]
    cnt += 1
  else
    break cnt = -1
  end
end
puts cnt

Measured memory_bytes: 9468
#include <iostream>
#define MAX_COUNT 200005
using namespace std;

int nums[MAX_COUNT] = {0};
int main(int argc, char const *argv[])
{
	int count;
	cin >> count;
	int xorall = 0;
	for (int i = 0; i < count; ++i)
	{
		cin >> nums[i];
		xorall ^= nums[i];
	}
	for (int i = 0; i < count; ++i)
	{
		cout << (xorall ^ nums[i]) << endl;
	}
	return 0;
}

Measured memory_bytes: 4316
#include <bits/stdc++.h>
using namespace std;
int main()
{	
	int A, B, C;
	cin >>A >>B >>C;

	if(A==B&&B!=C){
		cout <<"Yes" <<endl;
	}
	else if(B==C&&C!=A){
		cout <<"Yes" <<endl;
	}
	else if(C==A&&A!=B){
		cout <<"Yes" <<endl;
	}
	else{
		cout <<"No" <<endl;
	}
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,c;
	int q,w,e,ans;
	cin>>a>>b>>c;
	q=max(max(a,b),c);
	if(a==q) 
	{if(b>=c) w=b,e=c;
	else w=c,e=b;}
	if(b==q)
	{
		if(a>=c) w=a,e=c;
		else w=c,e=a;
	}
	if(c==q)
	{
		if(a>=b) w=a,e=b;
		else w=b,e=a;
	}
	ans=q-w+(w-e)/2;
//	cout<<ans<<endl;
	if((q-w)%2!=(q-e)%2) ans+=2;
	cout<<ans; 
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <math.h>
#include<iostream>
#include <string>
using namespace std;
typedef long long ll;
#define pb pushback
#define fr(i,n) for(int i=0;i<n;i++)
#define ifr(i,n) for(int i=n-1;i>=0;i--)


int main() {
    string x,y,z;
	cin >> x>> y>> z;
    string ans;
    if(x.substr(x.length()-1, 1)==y.substr(0, 1)&&y.substr(y.length()-1, 1)==z.substr(0, 1))ans="YES";
    else ans = "NO";
      cout << ans << endl;
}

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

using namespace std;

long long inf=1000000007;

int main(){
	string s;
	cin>>s;
	int a=0,b=0,c=0;

	for(auto at:s){
		if(at=='a') a++;
		else if(at=='b') b++;
		else c++;
	}

	if(abs(a-b)<=1 && abs(b-c)<=1 && abs(a-c)<=1) cout<<"YES"<<endl;
	else cout<<"NO"<<endl;

	return 0;
}


Measured memory_bytes: 3744
#include<stdio.h>
#include<string.h>
int main(void){
	int n;
	int i,j,h,k,len,lenn,sa,a,sam;
	int flg,cnt=0;
	char name[100],c;
	char ohuru[100];
	scanf("%d",&n);
	scanf("%s",name);
	lenn=strlen(name);
	for(i=0;i<n;i++){
		scanf("%s",ohuru);
		flg=1;
		len=strlen(ohuru);
		for(j=0;j<len;j++){
			if(name[0]==ohuru[j]){
				for(h=j+1;h<len;h++){
					if(name[1]==ohuru[h]){
						sa=h-j;
						/*printf("j=%d h=%d\n",j,h);
						printf("sa2=%d\n",sa);*/
						sam=sa;
						sa+=h;
						flg=1;
						for(k=2;k<lenn;k++){
							//printf("sa2=%d\n",sa);
							if(name[k]==ohuru[sa] && flg==1 && sa<=len){
								//printf("name[]=%d ohuru[]=%d\n",k,sa);
								c=ohuru[sa];
								/*printf("%c\n",c);
								printf("k=%d\n",k);*/
								if(k==lenn-1){
									flg=2;
									break;
								}
							}
							else if(name[k]!=ohuru[sa]){
								flg=0;
								//printf("muri\n");
								break;
							}
							sa+=sam;
						}
					}
					if(flg==2){
						break;
					}
				}
			}
			if(flg==2){
				break;
			}
		}
		if(flg==2){
			cnt++;
			/*printf("cnt=%d\n",cnt);
			printf("%s\n",ohuru);*/
		}
		//printf("\n");
	}
	printf("%d\n",cnt);
	return 0;
}

Measured memory_bytes: 600
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	
	int n; cin>>n;
	int arr[n];
	for(int i = 0; i < n; i++){
		cin>>arr[i];
	}
	int mi = 1000000; int co = 0;
	for(int i = 0; i <n; i++){
		if(arr[i] <= mi) co++;
		mi = min(arr[i],mi);
	}
	cout<<co<<"\n";
	
	
	
	
	
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cmath>
#include <set>
#include <queue>
#include <vector>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
using namespace std;

int main()
{
	int N;
	cin >> N;

	vector<unsigned long long> A(N);
	for (auto i = 0; i < N; ++i)
	{
		cin >> A[i];
	}

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

	cout << A[N - 1] - A[0] << endl;

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<double> p(n);
    double prev = 0;

    for (int i = 0; i < n; ++i) {
        double a;
        cin >> a;
        prev += (a+1)/2;
        p[i] = prev;
    }

    double mx = -1;
    for (int i = 0; i <= n-k; ++i) {
        double expected = (i == 0 ? p[k-1] : p[i+k-1] - p[i-1]);
        if (expected > mx)
            mx = expected;
    }
    printf("%.12f\n", mx);

    return 0;
}


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

using namespace std;

using ll = long long;
constexpr ll MOD = 1e9 + 7;
constexpr ll INF = 1e18;

int main() {
    ll n,k,Q;
    cin >> n >> k >> Q;
    vector<ll> A(n+1);
    for(ll i=0;i<Q;i++){
        ll x;cin>> x;
        A[x]++;
    }
    for(ll i=1;i<=n;i++){
        if(Q-A[i]>=k){
            cout << "No" << endl;
        }else{
            cout << "Yes" <<endl;
        }
    }
    return 0;
}

Measured memory_bytes: 1408
s = int(input())
ans = [0,0,0,0,0,0]
if s > 10**9:
    a = 10**9
    d = s//a + 1
    b = 1
    c = a*d - s
    if d > 10**9:
        d = s//a
        b = 0
        c = a*d - s
else:
    a = 1
    d = s
    b = 0
    c = 0
print(0,0,a,b,c,d)

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

typedef long long ll;
typedef pair<int, int> P;

int MOD = 1e9 + 7;
ll INF = 1e18;

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

int main(){
    int h, w; cin>>h>>w;
    int a[510][510];
    bool visited[510][510];
    for(int i=1; i<=h; i++){
        for(int j=1; j<=w; j++){
            cin>>a[i][j];
            visited[i][j]=false;
        }
    }

    for(int i=0; i<=w; i++) a[0][i]=MOD;
    for(int i=0; i<=h; i++) a[i][0]=MOD;
    for(int i=0; i<=w; i++) a[h+1][i]=MOD;
    for(int i=0; i<=h; i++) a[i][w+1]=MOD;

    int ans=0;
    vector<int> ans1(260000), ans2(260000), ans3(260000), ans4(260000);
    for(int i=1; i<=h; i++){
        for(int j=1; j<=w; j++){
            visited[i][j]=true;
            if(a[i][j] % 2 == 0) continue;

            bool flag=true;
            for(int k=0; k<4; k++){
                int ny=dy[k], nx=dx[k];

                if(a[i+ny][j+nx] != MOD && visited[i+ny][j+nx] == false){
                    if(a[i+ny][j+nx] % 2 == 1){
                        flag=false;
                        a[i][j]--;
                        a[i+ny][j+nx]++;
                        ans++;
                        ans1[ans]=i, ans2[ans]=j, ans3[ans]=i+ny, ans4[ans]=j+nx;
                        break;
                    }
                }
            }

            if(flag){
                if(j != w){
                    a[i][j]--;
                    a[i][j+1]++;
                    ans++;
                    ans1[ans]=i, ans2[ans]=j, ans3[ans]=i, ans4[ans]=j+1;
                }
                else if(i != h){
                    a[i][j]--;
                    a[i+1][j]++;
                    ans++;
                    ans1[ans]=i, ans2[ans]=j, ans3[ans]=i+1, ans4[ans]=j;
                }
            }
        }
    }

    cout << ans << endl;
    for(int i=1; i<=ans; i++){
        cout << ans1[i] << " " << ans2[i] << " " << ans3[i] << " " << ans4[i] << endl;
    }
}

Measured memory_bytes: 8960
/**
 *    author        : Sudipta Banik Trisha 
 *    created       : August 15, 2020 6:00 PM
 *    Problem Name  : A - Rainy Season
 *    Problem Limit : 2000 ms , 1024 MB
 *    Problem Url   : https://atcoder.jp/contests/abc175/tasks/abc175_a
 *    @genarated by : ai-virtual-assistant
**/

#include<bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);

    string s;
    cin >> s;
    int cnt=0;
    int len = s.length();
    if(s[0] == 'R' && s[1] == 'R' && s[2] == 'R') cout << "3" << endl;
    else if(s[0] == 'S' && s[1] == 'S' && s[2] == 'S') cout << "0" << endl;
    else if (s[0] == 'R' && s[1] == 'R' && s[2] == 'S') cout << "2" << endl;
    else if (s[0] == 'S' && s[1] == 'R' && s[2] == 'R') cout << "2" << endl;
    else
        cout << "1" << endl;



    return 0 ;
}


Measured memory_bytes: 3636
#include <algorithm>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <queue>
#include <stack>
#include <utility>
#include <vector>
using std::cerr;
using std::cin;
using std::cout;
using std::endl;

void OutputError(std::string s) {
  cerr << "\033[93m" << s << "\033[m" << endl;
  return;
}

int main(void) {
  cout << std::fixed << std::setprecision(10);
  cin.tie(0);
  std::ios::sync_with_stdio(false);
  int r, g, b;
  cin >> r >> g >> b;
  if ((r * 100 + g * 10 + b) % 4 == 0) {
    cout << "YES";
  } else {
    cout << "NO";
  }
  cout << endl;

  return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#include<cmath>
#define SF scanf
#define PF printf
#define MAXN 110
#define EPS 1e-7
using namespace std;
const double Pi=acos(-1);
struct node{
    double x,y;
    int id;
    node(){}
    node(double xx,double yy):x(xx),y(yy) {}
    node operator + (const node &a) const {
        return node(x+a.x,y+a.y);
    }
    node operator - (const node &a) const {
        return node(x-a.x,y-a.y);
    }
    node operator * (const double &t) const {
        return node(x*t,y*t);
    }
    double operator *(const node &a) const{
        return x*a.x+y*a.y;
    }
    double operator ^(const node &a) const{
        return x*a.y-y*a.x;
    }
    bool operator <(const node &a) const {
        return fabs(y-a.y)<EPS?x<a.x:y<a.y;
    }
}p[MAXN],l1[MAXN];
stack<node> s1,s;
double ans[MAXN];
int n,cnt1;
void solve(node a1[],int &cnt){
    s.push(p[1]);
    s1.push(p[1]);
    s1.push(p[2]);
    for(int i=3;i<=n;i++){
        while(!s.empty()&&((p[i]-s.top())^(s1.top()-s.top()))<-EPS){
            s.pop();
            s1.pop();
        }
        s.push(s1.top());
        s1.push(p[i]);
    }
    while(!s1.empty()){
        a1[++cnt]=s1.top();
        s1.pop();
    }
    while(!s.empty())
        s.pop();
}
bool cmp(node a,node b){
    return b<a;
}
double len(node a){
    return sqrt(a.x*a.x+a.y*a.y);
}
pair<long long,long long> b[MAXN];
bool check(){
    for(int i=1;i<=n;i++){
        b[i].first=(long long)(p[i].x);
        b[i].second=(long long)(p[i].y);
    }
    for(int i=2;i<n;i++){
        long long xx1=b[i].first-b[i-1].first;
        long long xx2=b[i+1].first-b[i].first;
        long long yy1=b[i].second-b[i-1].second;
        long long yy2=b[i+1].second-b[i].second;
        if(yy1*xx2!=yy2*xx1)
            return 0;
    }
    return 1;
}
int main(){
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);
    SF("%d",&n);
    for(int i=1;i<=n;i++){
        SF("%lf%lf",&p[i].x,&p[i].y);
        p[i].id=i;
    }
    sort(p+1,p+1+n);
    if(n==2){
        PF("0.500000\n");
        for(int i=2;i<n;i++)
            PF("0.000000\n");
        PF("0.500000\n");
        return 0;
    }
    solve(l1,cnt1);
    sort(p+1,p+1+n,cmp);
    cnt1--;
    solve(l1,cnt1);
    cnt1--;
    for(int i=1;i<=cnt1;i++){
        int las,nxt;
        if(i==1)
            las=cnt1;
        else
            las=i-1;
        if(i==cnt1)
            nxt=1;
        else
            nxt=i+1;
        double d=((l1[nxt]-l1[i])*(l1[las]-l1[i]))/(len(l1[nxt]-l1[i])*len(l1[las]-l1[i]));
        //PF("[%lf]",fabs((l1[nxt]-l1[i])*(l1[i]-l1[las])));
        d=acos(-d);
        ans[l1[i].id]=d/(2.0*Pi);
    }
    for(int i=1;i<=n;i++)
        PF("%.6lf\n",ans[i]);
}

Measured memory_bytes: 256
N=int(input())

a=[0]*N

x=1
while x*x<=N:
    y=1
    while x*x+y*y+x*y<=N:
        z=1
        while z*z+x*x+y*y+x*y+z*y+z*x<=N:
            a[z*z+x*x+y*y+x*y+z*y+z*x-1]+=1
            z+=1
        y+=1
    x+=1

for n in a:
    print(n)
    


Measured memory_bytes: 9252
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
 
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("-ffloat-store")
 
#define int  long long
#define rep(i,begin,end) for(__typeof(end)i=(begin)-((begin)>(end));i!=(end)-((begin)>(end));i+=1-2*((begin)>(end)))
#define F first
#define S second
#define sz(x) ((int)x.size())
#define pb push_back
#define pf push_front
#define eb emplace_back
#define all(v) (v).begin(), (v).end()
#define mod 1000000007
#define what_is(x) cerr << #x << " is " << x <<"\n";
#define sortA(v) sort(v.begin(), v.end())
#define sortD(v) sort(v.rbegin(), v.rend())
#define PI 3.14159265358979323846
#define vout(a) for(auto x:a) cout<<x<<" ";
#define INF 10000000000000000 //1e16
 
// #define ordered_set tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
 
 
// using namespace __gnu_pbds;
using namespace std;
 
using ll  = long long;
using vi  = vector<int>;
using pii = pair<int,int>;
using vii = vector<pii>;
using mi  = multiset<int>;
using mii = multiset<pii>;
 
int lcm(int a,int b) {return (a*(b/__gcd(a,b)));}



void solve()
{
    int n,m,t,i,k,r,l,u,v,w,j,s,sum=0,flag=0,count=0;
    string S,T,U; 
    // int a,b,x,y,z,c;
    cin>>n>>k;
    vi a(n);
    rep(i,0,n) cin>>a[i];
    if(k>=n)
    {
        cout<<"0";
        return;
    }
    sortD(a);
    rep(i,k,n)
    {
        sum+=a[i];
    }
    cout<<sum;
}

 

signed main()
{
    #ifndef ONLINE_JUDGE 
       freopen("input.txt","r",stdin);
       freopen("output.txt","w",stdout);
    #endif
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)
    {
        solve();
        if(t)cout<<"\n";
    }
    return 0;
}

Measured memory_bytes: 4748
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> VI;

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()

const int mod = 1e9 + 7;

int main() {
    int h, w, d;
    cin >> h >> w >> d;
    vector<P> place(h * w);
    rep (i, h) {
        vector<int> x(w);
        rep (j, w) {
            cin >> x[j];
            x[j]--;
        }
        rep (j, w) {
            place[x[j]] = make_pair(i, j);
        }
    }
    vector<vector<int>> dist(d);
    rep (i, d) {
        dist[i].push_back(0);
    }
    rep (i, h * w) {
        if (i / d == 0) {
            dist[i % d].push_back(0);
        } else {
            int x = abs(place[i].first - place[i-d].first);
            int y = abs(place[i].second - place[i-d].second);
            dist[i % d].push_back(x + y);
        }
    }
    rep (i, d) {
        rep (j, dist[i].size() - 1) {
            dist[i][j+1] += dist[i][j];
        }
    }
    int q;
    cin >> q;
    rep (i, q) {
        int start, goal;
        cin >> start >> goal;
        if (start == goal) {
            cout << 0 << endl;
            continue;
        }
        start--; goal--;
        int row = start % d;
        start /= d;
        goal /= d;
        cout << dist[row][goal+1] - dist[row][start+1] << endl;
    }
}




Measured memory_bytes: 6016
$debug = false
flag = ARGV.shift
if flag == "-d"
  $debug = true
end

def dputs str
  p str if $debug
end

def max(n, m)
  if n > m
    return n
  else
    return m
  end
end

def min(n, m)
  if n < m
    return n
  else
    return m
  end
end

def gets_all_int
  return gets.chomp.split.map{|v| v.to_i}
end

## start

A, B = gets_all_int

# sockets = A * n - (n - 1)

taps = 0
0.upto(B) do |n|
  if n == 0
    sockets = 1
  else
    sockets = A * n - (n - 1)
  end
  dputs "sockets = #{sockets}, n=#{n}"
  if sockets >= B
    taps = n
    break
  end
end

puts taps

Measured memory_bytes: 1788
n = int(input())
A = map(int, input().split())

pos = []
neg = []
for a in A:
    if 0 <= a:
        pos.append(a)
    else:
        neg.append(a)


ans = []
if pos:
    if not neg:
        pos.sort(reverse=True)
        neg.append(pos.pop())

    while len(pos) != 1:
        x = pos.pop()
        ans.append((neg[-1], x))
        neg[-1] -= x
else:
    neg.sort()
    pos.append(neg.pop())

pos = pos[0]
while neg:
    x = neg.pop()
    ans.append((pos, x))
    pos -= x

print(pos)
for row in ans:
    print(*row)

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

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

    int A, B, C;
    cin >> A >> B >> C;

    if ((A < C && C < B) || (B < C && C < A)) {
        cout << "Yes"  << '\n';
    } else {
        cout << "No"  << '\n';
    }


    return 0;
}


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

using namespace std;

typedef long long int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

ll N;
ll A[200005];

bool check(ll m) {
    stack<pll> stack;
    stack.push(pll(1, 1));
    REP(i, N - 1) {
        if (A[i] < A[i + 1])
            continue;
        if (m <= 1)
            return false;
        while (stack.size() > 0 && stack.top().first > A[i + 1])
            stack.pop();
        if (stack.top().first == A[i + 1])
            stack.top().second++;
        else
            stack.push(pll(A[i + 1], 2));

        while (stack.top().second > m) {
            ll nxt = stack.top().first - 1;
            stack.pop();
            if (stack.empty() || nxt <= 0)
                return false;
            if (stack.top().first == nxt)
                stack.top().second++;
            else
                stack.push(pll(nxt, 2));
        }
    }
    return true;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    REP(i, N) {
        cin >> A[i];
    }

    ll ok = INF, ng = 0;
    while (abs(ok - ng) > 1) {
        ll mid = (ok + ng) / 2;
        if (check(mid))
            ok = mid;
        else
            ng = mid;
    }
    cout << ok << endl;

    return 0;
}

Measured memory_bytes: 1792
P = [1 for _ in range(10**6)]
P[0]=0
P[1]=0
for i in range(2,10**3):
    for j in range(i*i,10**6,i):
        P[j] = 0
Q = []
for i in range(2,10**6):
    if P[i]==1:
        Q.append(i)
N = int(input())
C = {}
for q in Q:
    if N%q==0:
        C[q] = 0
        while N%q==0:
            N = N//q
            C[q] += 1
if N>1:
    C[N] = 1
cnt = 0
for q in C:
    k = C[q]
    n = 1
    while k>(n*(n+1))//2:
        n += 1
    if k==(n*(n+1))//2:
        cnt += n
    else:
        cnt += n-1
print(cnt)


Measured memory_bytes: 148860
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <queue>
typedef long long ll;
#define rep(i,n) for(int i = 0;i<n;++i)
#define repc(bit,k,n) for (int bit = (1<<k)-1;bit < (1<<n); bit = next_combination(bit))
#define repi(itr,vec) for(auto itr = vec.begin();itr!=vec.end();++itr)
using namespace std;
using Graph = vector<vector<int> >;

/* next combination
 * usage:repc(bit,k,n)
 * */
inline int next_combination(int sub) {
  int x = sub & -sub, y = sub + x;
  return (((sub & ~y) / x) >> 1) | y;
}

/* uniq
 * usage:uniq(vec)
 * */
void uniq(vector<int> &vec){
  sort(vec.begin(), vec.end());
  vec.erase(unique(vec.begin(), vec.end()), vec.end());
  return;
}

/* BinaryIndexedTree
 * usage:update and sum of 1~N
 * */
int N;
int bit[1000010];
void add(int a, int w) {
  for (int x = a; x <= N; x += x & -x) bit[x] += w;
}
int sum(int a) {
  int ret = 0;
  for (int x = a; x > 0; x -= x & -x) ret += bit[x];
  return ret;
}

/* DP
 * usage: chmin(dp[i],dp[i-1]+v);
 * */
const ll INF = 1LL << 60;
ll dp[100010];

template<class T> inline bool chmin(T& a, T b) {
      if (a > b) {
                a = b;
                        return true;
                            }
          return false;
}
template<class T> inline bool chmax(T& a, T b) {
      if (a < b) {
                a = b;
                        return true;
                            }
          return false;
}
int main(){
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
  string s;cin >> s;
  int ans = 0;
  rep(i,s.length()){
    ans+=int(s[i])%3;
  }
  if(ans%3==0)cout<<"Yes\n";
  else cout<< "No\n";

        return 0;
}

Measured memory_bytes: 3772
package main

import "fmt"

func main() {
	var w string
	fmt.Scan(&w)
	charCountMap := map[int32]int{}
	for _, char := range w {
		charCountMap[char]++
	}
	for _, count := range charCountMap {
		if count%2 != 0 {
			fmt.Println("No")
			return
		}
	}
	fmt.Println("Yes")
}


Measured memory_bytes: 1840
#include<stdio.h>
int main()
{
    long long int N,M,A[10000],i,sum=0,r;
    scanf("%lld%lld",&N,&M);
    for(i=0;i<M;i++)
    {
        scanf("%lld",&A[i]);
        sum=sum+A[i];
    }
    if(sum<=N)
        r=N-sum;
    else
        r=-1;
    printf("%lld",r);
    return 0;
}


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

int main() {
  string s;
  cin >> s;

  ll ans = 0;
  for (int i = 0; i < 1<<s.size()-1; ++i) {
    ll t = s[0] - '0';
    for (int j = 0; j < s.size()-1; ++j) {
      if(i&1<<j){
        ans += t;
        t = 0;
      }
      t = t * 10 + s[j + 1] - '0';
    }
    ans += t;
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
int main()
{
  int n;
  cin >> n;
  vector<ll> a(n);
  ll sum = 0;
  ll minus = 0;
  ll zero = 0;
  ll a_min = 1e9;
  REP(i,n){
    cin >> a[i];
    sum += abs(a[i]);
    a_min = min(a_min, abs(a[i]));
    if(a[i]==0) zero++;
    else if(a[i]<0) minus++;
  }
  
  cout << ((minus%2==0 || zero>0) ? sum : sum-2*a_min) << '\n'; 
  return 0;
}

Measured memory_bytes: 1024
#include <string>
#include <iostream>
#include <vector>
#include <stack>
#include <math.h>
#include <iomanip>
#include <queue>
#include <map>
#include <list>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define WHITE 0
#define GRAY 1
#define BLACK 2
#define MAX 50
#define LARGENUM 1000000007
#define INF 9223372036854775807
#define ull unsigned long long 
typedef pair <int, int> P;

int main(){
    int X, N, d = 1000, ans;
    bool flag;
    cin >> X >> N;
    int p[N];
    rep(i, N) cin >> p[i];
    for (int i = 101; i >= 0; i--){
        flag = true;
        rep(j, N) if (p[j] == i) flag = false;
        if (flag){
            if (d >= abs(X - i)) {
                d = abs(X - i);
                ans = i;
            }
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3164
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int N, X, T;
    int ans1, ans2;
    
    cin >> N >> X >> T;
    
    ans1 = N / X;
    ans2 = N % X;
    
    if(ans2 != 0){
        ans1=ans1+1;
    }
    
    ans1= ans1 * T;
    
    cout << ans1 << endl;
}


Measured memory_bytes: 3624
N = int(input())
A = map(int,input().split())

B = [0]
ans = 0
for a in A:
    B.append(B[-1]+a)

from collections import Counter
B = Counter(B).most_common()
for b in B:
    if b[1]>=2:
        ans += b[1]*(b[1]-1)//2
        
print(ans)


Measured memory_bytes: 40168
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
typedef double db;
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;

void factor(ll n,vector<ll> &d) {
	d.clear();
	for (ll i=1;i*i<=n;i++) if (n%i==0) {
		d.pb(i);
		if (n/i!=i) d.pb(n/i);
	}
}

vector<ll> d1,d2;
ll n; 

inline bool chk(ll d) {
	ll m=n;
	while (m%d==0) m/=d;
	return m%d==1;
}

int main() {
	scanf("%lld",&n);
	set<ll> ans;
	factor(n,d1),factor(n-1,d2);
	for (auto d:d1) if (d!=1&&chk(d)) ans.insert(d);
	for (auto d:d2) if (d!=1) ans.insert(d);
	printf("%d\n",SZ(ans));
	return 0;
}

Measured memory_bytes: 384